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) == MODIFY_EXPR
 136                    && TREE_OPERAND (stmt, 0) == result)
 137             {
 138               ret_expr = TREE_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                   || !lang_hooks.types_compatible_p (TREE_TYPE (found),
 162                                                      result_type))
 163                 return 0;
 164             }
 165           else if (TREE_CODE (stmt) == MODIFY_EXPR)
 166             {
 167               tree addr = get_base_address (TREE_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) == MODIFY_EXPR
 208               && TREE_OPERAND (*tp, 0) == result
 209               && TREE_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 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 /* Determine (pessimistically) whether DEST is available for NRV
 242    optimization, where DEST is expected to be the LHS of a modify
 243    expression where the RHS is a function returning an aggregate.
 244
 245    We search for a base VAR_DECL and look to see if it, or any of its
 246    subvars are clobbered.  Note that we could do better, for example, by
 247    attempting to doing points-to analysis on INDIRECT_REFs.  */
 248
 249 static bool
 250 dest_safe_for_nrv_p (tree dest)
 251 {
 252   switch (TREE_CODE (dest))
 253     {
 254       case VAR_DECL:
 255         {
 256           subvar_t subvar;
 257           if (is_call_clobbered (dest))
 258             return false;
 259           for (subvar = get_subvars_for_var (dest);
 260                subvar;
 261                subvar = subvar->next)
 262             if (is_call_clobbered (subvar->var))
 263               return false;
 264           return true;
 265         }
 266       case ARRAY_REF:
 267       case COMPONENT_REF:
 268         return dest_safe_for_nrv_p (TREE_OPERAND (dest, 0));
 269       default:
 270         return false;
 271     }
 272 }
 273
 274 /* Walk through the function looking for MODIFY_EXPRs with calls that
 275    return in memory on the RHS.  For each of these, determine whether it is
 276    safe to pass the address of the LHS as the return slot, and mark the
 277    call appropriately if so.
 278
 279    The NRV shares the return slot with a local variable in the callee; this
 280    optimization shares the return slot with the target of the call within
 281    the caller.  If the NRV is performed (which we can't know in general),
 282    this optimization is safe if the address of the target has not
 283    escaped prior to the call.  If it has, modifications to the local
 284    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 285
 286 static unsigned int
 287 execute_return_slot_opt (void)
 288 {
 289   basic_block bb;
 290
 291   FOR_EACH_BB (bb)
 292     {
 293       block_stmt_iterator i;
 294       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 295         {
 296           tree stmt = bsi_stmt (i);
 297           tree call;
 298
 299           if (TREE_CODE (stmt) == MODIFY_EXPR
 300               && (call = TREE_OPERAND (stmt, 1),
 301                   TREE_CODE (call) == CALL_EXPR)
 302               && !CALL_EXPR_RETURN_SLOT_OPT (call)
 303               && aggregate_value_p (call, call))
 304             /* Check if the location being assigned to is
 305                call-clobbered.  */
 306             CALL_EXPR_RETURN_SLOT_OPT (call) =
 307               dest_safe_for_nrv_p (TREE_OPERAND (stmt, 0)) ? 1 : 0;
 308         }
 309     }
 310   return 0;
 311 }
 312
 313 struct tree_opt_pass pass_return_slot =
 314 {
 315   "retslot",                            /* name */
 316   NULL,                                 /* gate */
 317   execute_return_slot_opt,              /* execute */
 318   NULL,                                 /* sub */
 319   NULL,                                 /* next */
 320   0,                                    /* static_pass_number */
 321   0,                                    /* tv_id */
 322   PROP_ssa | PROP_alias,                /* properties_required */
 323   0,                                    /* properties_provided */
 324   0,                                    /* properties_destroyed */
 325   0,                                    /* todo_flags_start */
 326   0,                                    /* todo_flags_finish */
 327   0                                     /* letter */
 328 };