gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009 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 walk_stmt_info *wi = (struct walk_stmt_info *) data;
  78   struct nrv_data *dp = (struct nrv_data *) wi->info;
  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   gimple_stmt_iterator gsi;
 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   /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
 120      non-GIMPLE.  */
 121   if (is_gimple_reg_type (result_type))
 122     return 0;
 123
 124   /* If the front end already did something like this, don't do it here.  */
 125   if (DECL_NAME (result))
 126     return 0;
 127
 128   /* Look through each block for assignments to the RESULT_DECL.  */
 129   FOR_EACH_BB (bb)
 130     {
 131       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 132         {
 133           gimple stmt = gsi_stmt (gsi);
 134           tree ret_val;
 135
 136           if (gimple_code (stmt) == GIMPLE_RETURN)
 137             {
 138               /* In a function with an aggregate return value, the
 139                  gimplifier has changed all non-empty RETURN_EXPRs to
 140                  return the RESULT_DECL.  */
 141               ret_val = gimple_return_retval (stmt);
 142               if (ret_val)
 143                 gcc_assert (ret_val == result);
 144             }
 145           else if (gimple_has_lhs (stmt)
 146                    && gimple_get_lhs (stmt) == result)
 147             {
 148               tree rhs;
 149
 150               if (!gimple_assign_copy_p (stmt))
 151                 return 0;
 152
 153               rhs = gimple_assign_rhs1 (stmt);
 154
 155               /* Now verify that this return statement uses the same value
 156                  as any previously encountered return statement.  */
 157               if (found != NULL)
 158                 {
 159                   /* If we found a return statement using a different variable
 160                      than previous return statements, then we can not perform
 161                      NRV optimizations.  */
 162                   if (found != rhs)
 163                     return 0;
 164                 }
 165               else
 166                 found = rhs;
 167
 168               /* The returned value must be a local automatic variable of the
 169                  same type and alignment as the function's result.  */
 170               if (TREE_CODE (found) != VAR_DECL
 171                   || TREE_THIS_VOLATILE (found)
 172                   || DECL_CONTEXT (found) != current_function_decl
 173                   || TREE_STATIC (found)
 174                   || TREE_ADDRESSABLE (found)
 175                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 176                   || !useless_type_conversion_p (result_type,
 177                                                 TREE_TYPE (found)))
 178                 return 0;
 179             }
 180           else if (gimple_has_lhs (stmt))
 181             {
 182               tree addr = get_base_address (gimple_get_lhs (stmt));
 183                /* If there's any MODIFY of component of RESULT,
 184                   then bail out.  */
 185               if (addr && addr == result)
 186                 return 0;
 187             }
 188         }
 189     }
 190
 191   if (!found)
 192     return 0;
 193
 194   /* If dumping details, then note once and only the NRV replacement.  */
 195   if (dump_file && (dump_flags & TDF_DETAILS))
 196     {
 197       fprintf (dump_file, "NRV Replaced: ");
 198       print_generic_expr (dump_file, found, dump_flags);
 199       fprintf (dump_file, "  with: ");
 200       print_generic_expr (dump_file, result, dump_flags);
 201       fprintf (dump_file, "\n");
 202     }
 203
 204   /* At this point we know that all the return statements return the
 205      same local which has suitable attributes for NRV.   Copy debugging
 206      information from FOUND to RESULT if it will be useful.  But don't set
 207      DECL_ABSTRACT_ORIGIN to point at another function.  */
 208   if (!DECL_IGNORED_P (found)
 209       && !(DECL_ABSTRACT_ORIGIN (found)
 210            && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
 211     {
 212       DECL_NAME (result) = DECL_NAME (found);
 213       DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 214       DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 215     }
 216
 217   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 218
 219   /* Now walk through the function changing all references to VAR to be
 220      RESULT.  */
 221   data.var = found;
 222   data.result = result;
 223   FOR_EACH_BB (bb)
 224     {
 225       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 226         {
 227           gimple stmt = gsi_stmt (gsi);
 228           /* If this is a copy from VAR to RESULT, remove it.  */
 229           if (gimple_assign_copy_p (stmt)
 230               && gimple_assign_lhs (stmt) == result
 231               && gimple_assign_rhs1 (stmt) == found)
 232             gsi_remove (&gsi, true);
 233           else
 234             {
 235               struct walk_stmt_info wi;
 236               memset (&wi, 0, sizeof (wi));
 237               wi.info = &data;
 238               walk_gimple_op (stmt, finalize_nrv_r, &wi);
 239               gsi_next (&gsi);
 240             }
 241         }
 242     }
 243
 244   /* FOUND is no longer used.  Ensure it gets removed.  */
 245   var_ann (found)->used = 0;
 246   return 0;
 247 }
 248
 249 static bool
 250 gate_pass_return_slot (void)
 251 {
 252   return optimize > 0;
 253 }
 254
 255 struct gimple_opt_pass pass_nrv =
 256 {
 257  {
 258   GIMPLE_PASS,
 259   "nrv",                                /* name */
 260   gate_pass_return_slot,                /* gate */
 261   tree_nrv,                             /* execute */
 262   NULL,                                 /* sub */
 263   NULL,                                 /* next */
 264   0,                                    /* static_pass_number */
 265   TV_TREE_NRV,                          /* tv_id */
 266   PROP_cfg,                             /* properties_required */
 267   0,                                    /* properties_provided */
 268   0,                                    /* properties_destroyed */
 269   0,                                    /* todo_flags_start */
 270   TODO_dump_func | TODO_ggc_collect                     /* todo_flags_finish */
 271  }
 272 };
 273
 274 /* Determine (pessimistically) whether DEST is available for NRV
 275    optimization, where DEST is expected to be the LHS of a modify
 276    expression where the RHS is a function returning an aggregate.
 277
 278    We search for a base VAR_DECL and look to see if it is call clobbered.
 279    Note that we could do better, for example, by
 280    attempting to doing points-to analysis on INDIRECT_REFs.  */
 281
 282 static bool
 283 dest_safe_for_nrv_p (tree dest)
 284 {
 285   while (handled_component_p (dest))
 286     dest = TREE_OPERAND (dest, 0);
 287
 288   if (! SSA_VAR_P (dest))
 289     return false;
 290
 291   if (TREE_CODE (dest) == SSA_NAME)
 292     dest = SSA_NAME_VAR (dest);
 293
 294   if (is_call_used (dest))
 295     return false;
 296
 297   return true;
 298 }
 299
 300 /* Walk through the function looking for GIMPLE_ASSIGNs with calls that
 301    return in memory on the RHS.  For each of these, determine whether it is
 302    safe to pass the address of the LHS as the return slot, and mark the
 303    call appropriately if so.
 304
 305    The NRV shares the return slot with a local variable in the callee; this
 306    optimization shares the return slot with the target of the call within
 307    the caller.  If the NRV is performed (which we can't know in general),
 308    this optimization is safe if the address of the target has not
 309    escaped prior to the call.  If it has, modifications to the local
 310    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 311
 312 static unsigned int
 313 execute_return_slot_opt (void)
 314 {
 315   basic_block bb;
 316
 317   FOR_EACH_BB (bb)
 318     {
 319       gimple_stmt_iterator gsi;
 320       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 321         {
 322           gimple stmt = gsi_stmt (gsi);
 323           bool slot_opt_p;
 324
 325           if (is_gimple_call (stmt)
 326               && gimple_call_lhs (stmt)
 327               && !gimple_call_return_slot_opt_p (stmt)
 328               && aggregate_value_p (TREE_TYPE (gimple_call_lhs (stmt)),
 329                                     gimple_call_fndecl (stmt))
 330              )
 331             {
 332               /* Check if the location being assigned to is
 333                  call-clobbered.  */
 334               slot_opt_p = dest_safe_for_nrv_p (gimple_call_lhs (stmt));
 335               gimple_call_set_return_slot_opt (stmt, slot_opt_p);
 336             }
 337         }
 338     }
 339   return 0;
 340 }
 341
 342 struct gimple_opt_pass pass_return_slot =
 343 {
 344  {
 345   GIMPLE_PASS,
 346   "retslot",                            /* name */
 347   NULL,                                 /* gate */
 348   execute_return_slot_opt,              /* execute */
 349   NULL,                                 /* sub */
 350   NULL,                                 /* next */
 351   0,                                    /* static_pass_number */
 352   TV_NONE,                              /* tv_id */
 353   PROP_ssa | PROP_alias,                /* properties_required */
 354   0,                                    /* properties_provided */
 355   0,                                    /* properties_destroyed */
 356   0,                                    /* todo_flags_start */
 357   0                                     /* todo_flags_finish */
 358  }
 359 };