gcc/tree-nrv.c

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