gnu/dist/gcc4/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           else if (TREE_CODE (stmt) == MODIFY_EXPR)
 167             {
 168               tree addr = get_base_address (TREE_OPERAND (stmt, 0));
 169                /* If there's any MODIFY of component of RESULT,
 170                   then bail out.  */
 171               if (addr && addr == result)
 172                 return;
 173             }
 174         }
 175     }
 176
 177   if (!found)
 178     return;
 179
 180   /* If dumping details, then note once and only the NRV replacement.  */
 181   if (dump_file && (dump_flags & TDF_DETAILS))
 182     {
 183       fprintf (dump_file, "NRV Replaced: ");
 184       print_generic_expr (dump_file, found, dump_flags);
 185       fprintf (dump_file, "  with: ");
 186       print_generic_expr (dump_file, result, dump_flags);
 187       fprintf (dump_file, "\n");
 188     }
 189
 190   /* At this point we know that all the return statements return the
 191      same local which has suitable attributes for NRV.   Copy debugging
 192      information from FOUND to RESULT.  */
 193   DECL_NAME (result) = DECL_NAME (found);
 194   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 195   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 196   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 197
 198   /* Now walk through the function changing all references to VAR to be
 199      RESULT.  */
 200   data.var = found;
 201   data.result = result;
 202   FOR_EACH_BB (bb)
 203     {
 204       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 205         {
 206           tree *tp = bsi_stmt_ptr (bsi);
 207           /* If this is a copy from VAR to RESULT, remove it.  */
 208           if (TREE_CODE (*tp) == MODIFY_EXPR
 209               && TREE_OPERAND (*tp, 0) == result
 210               && TREE_OPERAND (*tp, 1) == found)
 211             bsi_remove (&bsi);
 212           else
 213             {
 214               walk_tree (tp, finalize_nrv_r, &data, 0);
 215               bsi_next (&bsi);
 216             }
 217         }
 218     }
 219
 220   /* FOUND is no longer used.  Ensure it gets removed.  */
 221   var_ann (found)->used = 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 /* Walk through the function looking for MODIFY_EXPRs with calls that
 242    return in memory on the RHS.  For each of these, determine whether it is
 243    safe to pass the address of the LHS as the return slot, and mark the
 244    call appropriately if so.
 245
 246    The NRV shares the return slot with a local variable in the callee; this
 247    optimization shares the return slot with the target of the call within
 248    the caller.  If the NRV is performed (which we can't know in general),
 249    this optimization is safe if the address of the target has not
 250    escaped prior to the call.  If it has, modifications to the local
 251    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 252
 253 static void
 254 execute_return_slot_opt (void)
 255 {
 256   basic_block bb;
 257
 258   FOR_EACH_BB (bb)
 259     {
 260       block_stmt_iterator i;
 261       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 262         {
 263           tree stmt = bsi_stmt (i);
 264           tree call;
 265
 266           if (TREE_CODE (stmt) == MODIFY_EXPR
 267               && (call = TREE_OPERAND (stmt, 1),
 268                   TREE_CODE (call) == CALL_EXPR)
 269               && !CALL_EXPR_RETURN_SLOT_OPT (call)
 270               && aggregate_value_p (call, call))
 271             {
 272               def_operand_p def_p;
 273               ssa_op_iter op_iter;
 274
 275               /* We determine whether or not the LHS address escapes by
 276                  asking whether it is call clobbered.  When the LHS isn't a
 277                  simple decl, we need to check the VDEFs, so it's simplest
 278                  to just loop through all the DEFs.  */
 279               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
 280                 {
 281                   tree def = DEF_FROM_PTR (def_p);
 282                   if (TREE_CODE (def) == SSA_NAME)
 283                     def = SSA_NAME_VAR (def);
 284                   if (is_call_clobbered (def))
 285                     goto unsafe;
 286                 }
 287
 288               /* No defs are call clobbered, so the optimization is safe.  */
 289               CALL_EXPR_RETURN_SLOT_OPT (call) = 1;
 290               /* This is too late to mark the target addressable like we do
 291                  in gimplify_modify_expr_rhs, but that's OK; anything that
 292                  wasn't already addressable was handled there.  */
 293
 294               unsafe:;
 295             }
 296         }
 297     }
 298 }
 299
 300 struct tree_opt_pass pass_return_slot =
 301 {
 302   "retslot",                            /* name */
 303   NULL,                                 /* gate */
 304   execute_return_slot_opt,              /* execute */
 305   NULL,                                 /* sub */
 306   NULL,                                 /* next */
 307   0,                                    /* static_pass_number */
 308   0,                                    /* tv_id */
 309   PROP_ssa | PROP_alias,                /* properties_required */
 310   0,                                    /* properties_provided */
 311   0,                                    /* properties_destroyed */
 312   0,                                    /* todo_flags_start */
 313   0,                                    /* todo_flags_finish */
 314   0                                     /* letter */
 315 };