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, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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   /* If this is a RETURN_EXPR, set the expression being returned to RESULT.  */
  85   else if (TREE_CODE (*tp) == RETURN_EXPR)
  86     TREE_OPERAND (*tp, 0) = dp->result;
  87
  88   /* Otherwise replace all occurrences of VAR with RESULT.  */
  89   else if (*tp == dp->var)
  90     *tp = dp->result;
  91
  92   /* Keep iterating.  */
  93   return NULL_TREE;
  94 }
  95
  96 /* Main entry point for return value optimizations.
  97
  98    If this function always returns the same local variable, and that
  99    local variable is an aggregate type, then replace the variable with
 100    the function's DECL_RESULT.
 101
 102    This is the equivalent of the C++ named return value optimization
 103    applied to optimized trees in a language independent form.  If we
 104    ever encounter languages which prevent this kind of optimization,
 105    then we could either have the languages register the optimization or
 106    we could change the gating function to check the current language.  */
 107
 108 static void
 109 tree_nrv (void)
 110 {
 111   tree result = DECL_RESULT (current_function_decl);
 112   tree result_type = TREE_TYPE (result);
 113   tree found = NULL;
 114   basic_block bb;
 115   struct nrv_data data;
 116
 117   /* If this function does not return an aggregate type in memory, then
 118      there is nothing to do.  */
 119   if (!aggregate_value_p (result, current_function_decl))
 120     return;
 121
 122   /* Look through each block for suitable return expressions.   RETURN_EXPRs
 123      end basic blocks, so we only have to look at the last statement in
 124      each block.  That makes this very fast.  */
 125   FOR_EACH_BB (bb)
 126     {
 127       tree stmt = last_stmt (bb);
 128
 129       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
 130         {
 131           tree ret_expr = TREE_OPERAND (stmt, 0);
 132
 133           /* This probably should not happen, but just to be safe do
 134              not perform NRV optimizations if only some of the return
 135              statement return a value.  */
 136           if (!ret_expr
 137               || TREE_CODE (ret_expr) != MODIFY_EXPR
 138               || TREE_CODE (TREE_OPERAND (ret_expr, 0)) != RESULT_DECL)
 139             return;
 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 != TREE_OPERAND (ret_expr, 1))
 149                 return;
 150             }
 151           else
 152             found = TREE_OPERAND (ret_expr, 1);
 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   if (!found)
 169     return;
 170
 171   /* If dumping details, then note once and only the NRV replacement.  */
 172   if (dump_file && (dump_flags & TDF_DETAILS))
 173     {
 174       fprintf (dump_file, "NRV Replaced: ");
 175       print_generic_expr (dump_file, found, dump_flags);
 176       fprintf (dump_file, "  with: ");
 177       print_generic_expr (dump_file, result, dump_flags);
 178       fprintf (dump_file, "\n");
 179     }
 180
 181   /* At this point we know that all the return statements return the
 182      same local which has suitable attributes for NRV.   Copy debugging
 183      information from FOUND to RESULT.  */
 184   DECL_NAME (result) = DECL_NAME (found);
 185   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 186   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 187   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 188
 189   /* Now walk through the function changing all references to VAR to be
 190      RESULT.  */
 191   data.var = found;
 192   data.result = result;
 193   FOR_EACH_BB (bb)
 194     {
 195       block_stmt_iterator bsi;
 196
 197       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 198         walk_tree (bsi_stmt_ptr (bsi), finalize_nrv_r, &data, 0);
 199     }
 200
 201   /* FOUND is no longer used.  Ensure it gets removed.  */
 202   var_ann (found)->used = 0;
 203 }
 204
 205 struct tree_opt_pass pass_nrv =
 206 {
 207   "nrv",                                /* name */
 208   NULL,                                 /* gate */
 209   tree_nrv,                             /* execute */
 210   NULL,                                 /* sub */
 211   NULL,                                 /* next */
 212   0,                                    /* static_pass_number */
 213   TV_TREE_NRV,                          /* tv_id */
 214   PROP_cfg,                             /* properties_required */
 215   0,                                    /* properties_provided */
 216   0,                                    /* properties_destroyed */
 217   0,                                    /* todo_flags_start */
 218   TODO_dump_func | TODO_ggc_collect,                    /* todo_flags_finish */
 219   0                                     /* letter */
 220 };
 221
 222 /* Walk through the function looking for MODIFY_EXPRs with calls that
 223    return in memory on the RHS.  For each of these, determine whether it is
 224    safe to pass the address of the LHS as the return slot, and mark the
 225    call appropriately if so.
 226
 227    The NRV shares the return slot with a local variable in the callee; this
 228    optimization shares the return slot with the target of the call within
 229    the caller.  If the NRV is performed (which we can't know in general),
 230    this optimization is safe if the address of the target has not
 231    escaped prior to the call.  If it has, modifications to the local
 232    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 233
 234 static void
 235 execute_return_slot_opt (void)
 236 {
 237   basic_block bb;
 238
 239   FOR_EACH_BB (bb)
 240     {
 241       block_stmt_iterator i;
 242       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 243         {
 244           tree stmt = bsi_stmt (i);
 245           tree call;
 246
 247           if (TREE_CODE (stmt) == MODIFY_EXPR
 248               && (call = TREE_OPERAND (stmt, 1),
 249                   TREE_CODE (call) == CALL_EXPR)
 250               && !CALL_EXPR_RETURN_SLOT_OPT (call)
 251               && aggregate_value_p (call, call))
 252             {
 253               def_operand_p def_p;
 254               ssa_op_iter op_iter;
 255
 256               /* We determine whether or not the LHS address escapes by
 257                  asking whether it is call clobbered.  When the LHS isn't a
 258                  simple decl, we need to check the VDEFs, so it's simplest
 259                  to just loop through all the DEFs.  */
 260               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
 261                 {
 262                   tree def = DEF_FROM_PTR (def_p);
 263                   if (TREE_CODE (def) == SSA_NAME)
 264                     def = SSA_NAME_VAR (def);
 265                   if (is_call_clobbered (def))
 266                     goto unsafe;
 267                 }
 268
 269               /* No defs are call clobbered, so the optimization is safe.  */
 270               CALL_EXPR_RETURN_SLOT_OPT (call) = 1;
 271               /* This is too late to mark the target addressable like we do
 272                  in gimplify_modify_expr_rhs, but that's OK; anything that
 273                  wasn't already addressable was handled there.  */
 274
 275               unsafe:;
 276             }
 277         }
 278     }
 279 }
 280
 281 struct tree_opt_pass pass_return_slot =
 282 {
 283   "retslot",                            /* name */
 284   NULL,                                 /* gate */
 285   execute_return_slot_opt,              /* execute */
 286   NULL,                                 /* sub */
 287   NULL,                                 /* next */
 288   0,                                    /* static_pass_number */
 289   0,                                    /* tv_id */
 290   PROP_ssa | PROP_alias,                /* properties_required */
 291   0,                                    /* properties_provided */
 292   0,                                    /* properties_destroyed */
 293   0,                                    /* todo_flags_start */
 294   0,                                    /* todo_flags_finish */
 295   0                                     /* letter */
 296 };