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