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