gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004, 2005, 2007, 2008 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   /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
 119      non-GIMPLE.  */
 120   if (is_gimple_reg_type (result_type))
 121     return 0;
 122
 123   /* Look through each block for assignments to the RESULT_DECL.  */
 124   FOR_EACH_BB (bb)
 125     {
 126       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 127         {
 128           tree stmt = bsi_stmt (bsi);
 129           tree ret_expr;
 130
 131           if (TREE_CODE (stmt) == RETURN_EXPR)
 132             {
 133               /* In a function with an aggregate return value, the
 134                  gimplifier has changed all non-empty RETURN_EXPRs to
 135                  return the RESULT_DECL.  */
 136               ret_expr = TREE_OPERAND (stmt, 0);
 137               if (ret_expr)
 138                 gcc_assert (ret_expr == result);
 139             }
 140           else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 141                    && GIMPLE_STMT_OPERAND (stmt, 0) == result)
 142             {
 143               ret_expr = GIMPLE_STMT_OPERAND (stmt, 1);
 144
 145               /* Now verify that this return statement uses the same value
 146                  as any previously encountered return statement.  */
 147               if (found != NULL)
 148                 {
 149                   /* If we found a return statement using a different variable
 150                      than previous return statements, then we can not perform
 151                      NRV optimizations.  */
 152                   if (found != ret_expr)
 153                     return 0;
 154                 }
 155               else
 156                 found = ret_expr;
 157
 158               /* The returned value must be a local automatic variable of the
 159                  same type and alignment as the function's result.  */
 160               if (TREE_CODE (found) != VAR_DECL
 161                   || TREE_THIS_VOLATILE (found)
 162                   || DECL_CONTEXT (found) != current_function_decl
 163                   || TREE_STATIC (found)
 164                   || TREE_ADDRESSABLE (found)
 165                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 166                   || !useless_type_conversion_p (result_type,
 167                                                 TREE_TYPE (found)))
 168                 return 0;
 169             }
 170           else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 171             {
 172               tree addr = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 173                /* If there's any MODIFY of component of RESULT,
 174                   then bail out.  */
 175               if (addr && addr == result)
 176                 return 0;
 177             }
 178         }
 179     }
 180
 181   if (!found)
 182     return 0;
 183
 184   /* If dumping details, then note once and only the NRV replacement.  */
 185   if (dump_file && (dump_flags & TDF_DETAILS))
 186     {
 187       fprintf (dump_file, "NRV Replaced: ");
 188       print_generic_expr (dump_file, found, dump_flags);
 189       fprintf (dump_file, "  with: ");
 190       print_generic_expr (dump_file, result, dump_flags);
 191       fprintf (dump_file, "\n");
 192     }
 193
 194   /* At this point we know that all the return statements return the
 195      same local which has suitable attributes for NRV.   Copy debugging
 196      information from FOUND to RESULT.  */
 197   DECL_NAME (result) = DECL_NAME (found);
 198   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 199   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 200   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 201
 202   /* Now walk through the function changing all references to VAR to be
 203      RESULT.  */
 204   data.var = found;
 205   data.result = result;
 206   FOR_EACH_BB (bb)
 207     {
 208       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 209         {
 210           tree *tp = bsi_stmt_ptr (bsi);
 211           /* If this is a copy from VAR to RESULT, remove it.  */
 212           if (TREE_CODE (*tp) == GIMPLE_MODIFY_STMT
 213               && GIMPLE_STMT_OPERAND (*tp, 0) == result
 214               && GIMPLE_STMT_OPERAND (*tp, 1) == found)
 215             bsi_remove (&bsi, true);
 216           else
 217             {
 218               walk_tree (tp, finalize_nrv_r, &data, 0);
 219               bsi_next (&bsi);
 220             }
 221         }
 222     }
 223
 224   /* FOUND is no longer used.  Ensure it gets removed.  */
 225   var_ann (found)->used = 0;
 226   return 0;
 227 }
 228
 229 struct gimple_opt_pass pass_nrv =
 230 {
 231  {
 232   GIMPLE_PASS,
 233   "nrv",                                /* name */
 234   NULL,                                 /* gate */
 235   tree_nrv,                             /* execute */
 236   NULL,                                 /* sub */
 237   NULL,                                 /* next */
 238   0,                                    /* static_pass_number */
 239   TV_TREE_NRV,                          /* tv_id */
 240   PROP_cfg,                             /* properties_required */
 241   0,                                    /* properties_provided */
 242   0,                                    /* properties_destroyed */
 243   0,                                    /* todo_flags_start */
 244   TODO_dump_func | TODO_ggc_collect                     /* todo_flags_finish */
 245  }
 246 };
 247
 248 /* Determine (pessimistically) whether DEST is available for NRV
 249    optimization, where DEST is expected to be the LHS of a modify
 250    expression where the RHS is a function returning an aggregate.
 251
 252    We search for a base VAR_DECL and look to see if it is call clobbered.
 253    Note that we could do better, for example, by
 254    attempting to doing points-to analysis on INDIRECT_REFs.  */
 255
 256 static bool
 257 dest_safe_for_nrv_p (tree dest)
 258 {
 259   while (handled_component_p (dest))
 260     dest = TREE_OPERAND (dest, 0);
 261
 262   if (! SSA_VAR_P (dest))
 263     return false;
 264
 265   if (TREE_CODE (dest) == SSA_NAME)
 266     dest = SSA_NAME_VAR (dest);
 267
 268   if (is_call_used (dest))
 269     return false;
 270
 271   return true;
 272 }
 273
 274 /* Walk through the function looking for GIMPLE_MODIFY_STMTs 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) == GIMPLE_MODIFY_STMT
 300               && (call = GIMPLE_STMT_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 (GIMPLE_STMT_OPERAND (stmt, 0)) ? 1 : 0;
 308         }
 309     }
 310   return 0;
 311 }
 312
 313 struct gimple_opt_pass pass_return_slot =
 314 {
 315  {
 316   GIMPLE_PASS,
 317   "retslot",                            /* name */
 318   NULL,                                 /* gate */
 319   execute_return_slot_opt,              /* execute */
 320   NULL,                                 /* sub */
 321   NULL,                                 /* next */
 322   0,                                    /* static_pass_number */
 323   0,                                    /* tv_id */
 324   PROP_ssa | PROP_alias,                /* properties_required */
 325   0,                                    /* properties_provided */
 326   0,                                    /* properties_destroyed */
 327   0,                                    /* todo_flags_start */
 328   0                                     /* todo_flags_finish */
 329  }
 330 };