gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "function.h"
  27 #include "basic-block.h"
  28 #include "diagnostic.h"
  29 #include "tree-pretty-print.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 #include "flags.h"      /* For "optimize" in gate_pass_return_slot.
  36                            FIXME: That should be up to the pass manager,
  37                            but pass_nrv is not in pass_all_optimizations.  */
  38
  39 /* This file implements return value optimizations for functions which
  40    return aggregate types.
  41
  42    Basically this pass searches the function for return statements which
  43    return a local aggregate.  When converted to RTL such statements will
  44    generate a copy from the local aggregate to final return value destination
  45    mandated by the target's ABI.
  46
  47    That copy can often be avoided by directly constructing the return value
  48    into the final destination mandated by the target's ABI.
  49
  50    This is basically a generic equivalent to the C++ front-end's
  51    Named Return Value optimization.  */
  52
  53 struct nrv_data
  54 {
  55   /* This is the temporary (a VAR_DECL) which appears in all of
  56      this function's RETURN_EXPR statements.  */
  57   tree var;
  58
  59   /* This is the function's RESULT_DECL.  We will replace all occurrences
  60      of VAR with RESULT_DECL when we apply this optimization.  */
  61   tree result;
  62   int modified;
  63 };
  64
  65 static tree finalize_nrv_r (tree *, int *, void *);
  66
  67 /* Callback for the tree walker.
  68
  69    If TP refers to a RETURN_EXPR, then set the expression being returned
  70    to nrv_data->result.
  71
  72    If TP refers to nrv_data->var, then replace nrv_data->var with
  73    nrv_data->result.
  74
  75    If we reach a node where we know all the subtrees are uninteresting,
  76    then set *WALK_SUBTREES to zero.  */
  77
  78 static tree
  79 finalize_nrv_r (tree *tp, int *walk_subtrees, void *data)
  80 {
  81   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
  82   struct nrv_data *dp = (struct nrv_data *) wi->info;
  83
  84   /* No need to walk into types.  */
  85   if (TYPE_P (*tp))
  86     *walk_subtrees = 0;
  87
  88   /* Otherwise replace all occurrences of VAR with RESULT.  */
  89   else if (*tp == dp->var)
  90     {
  91       *tp = dp->result;
  92       dp->modified = 1;
  93     }
  94
  95   /* Keep iterating.  */
  96   return NULL_TREE;
  97 }
  98
  99 /* Main entry point for return value optimizations.
 100
 101    If this function always returns the same local variable, and that
 102    local variable is an aggregate type, then replace the variable with
 103    the function's DECL_RESULT.
 104
 105    This is the equivalent of the C++ named return value optimization
 106    applied to optimized trees in a language independent form.  If we
 107    ever encounter languages which prevent this kind of optimization,
 108    then we could either have the languages register the optimization or
 109    we could change the gating function to check the current language.  */
 110
 111 static unsigned int
 112 tree_nrv (void)
 113 {
 114   tree result = DECL_RESULT (current_function_decl);
 115   tree result_type = TREE_TYPE (result);
 116   tree found = NULL;
 117   basic_block bb;
 118   gimple_stmt_iterator gsi;
 119   struct nrv_data data;
 120
 121   /* If this function does not return an aggregate type in memory, then
 122      there is nothing to do.  */
 123   if (!aggregate_value_p (result, current_function_decl))
 124     return 0;
 125
 126   /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
 127      non-GIMPLE.  */
 128   if (is_gimple_reg_type (result_type))
 129     return 0;
 130
 131   /* If the front end already did something like this, don't do it here.  */
 132   if (DECL_NAME (result))
 133     return 0;
 134
 135   /* If the result has its address taken then it might be modified
 136      by means not detected in the following loop.  Bail out in this
 137      case.  */
 138   if (TREE_ADDRESSABLE (result))
 139     return 0;
 140
 141   /* Look through each block for assignments to the RESULT_DECL.  */
 142   FOR_EACH_BB (bb)
 143     {
 144       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 145         {
 146           gimple stmt = gsi_stmt (gsi);
 147           tree ret_val;
 148
 149           if (gimple_code (stmt) == GIMPLE_RETURN)
 150             {
 151               /* In a function with an aggregate return value, the
 152                  gimplifier has changed all non-empty RETURN_EXPRs to
 153                  return the RESULT_DECL.  */
 154               ret_val = gimple_return_retval (stmt);
 155               if (ret_val)
 156                 gcc_assert (ret_val == result);
 157             }
 158           else if (gimple_has_lhs (stmt)
 159                    && gimple_get_lhs (stmt) == result)
 160             {
 161               tree rhs;
 162
 163               if (!gimple_assign_copy_p (stmt))
 164                 return 0;
 165
 166               rhs = gimple_assign_rhs1 (stmt);
 167
 168               /* Now verify that this return statement uses the same value
 169                  as any previously encountered return statement.  */
 170               if (found != NULL)
 171                 {
 172                   /* If we found a return statement using a different variable
 173                      than previous return statements, then we can not perform
 174                      NRV optimizations.  */
 175                   if (found != rhs)
 176                     return 0;
 177                 }
 178               else
 179                 found = rhs;
 180
 181               /* The returned value must be a local automatic variable of the
 182                  same type and alignment as the function's result.  */
 183               if (TREE_CODE (found) != VAR_DECL
 184                   || TREE_THIS_VOLATILE (found)
 185                   || DECL_CONTEXT (found) != current_function_decl
 186                   || TREE_STATIC (found)
 187                   || TREE_ADDRESSABLE (found)
 188                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 189                   || !useless_type_conversion_p (result_type,
 190                                                  TREE_TYPE (found)))
 191                 return 0;
 192             }
 193           else if (gimple_has_lhs (stmt))
 194             {
 195               tree addr = get_base_address (gimple_get_lhs (stmt));
 196                /* If there's any MODIFY of component of RESULT,
 197                   then bail out.  */
 198               if (addr && addr == result)
 199                 return 0;
 200             }
 201         }
 202     }
 203
 204   if (!found)
 205     return 0;
 206
 207   /* If dumping details, then note once and only the NRV replacement.  */
 208   if (dump_file && (dump_flags & TDF_DETAILS))
 209     {
 210       fprintf (dump_file, "NRV Replaced: ");
 211       print_generic_expr (dump_file, found, dump_flags);
 212       fprintf (dump_file, "  with: ");
 213       print_generic_expr (dump_file, result, dump_flags);
 214       fprintf (dump_file, "\n");
 215     }
 216
 217   /* At this point we know that all the return statements return the
 218      same local which has suitable attributes for NRV.   Copy debugging
 219      information from FOUND to RESULT if it will be useful.  But don't set
 220      DECL_ABSTRACT_ORIGIN to point at another function.  */
 221   if (!DECL_IGNORED_P (found)
 222       && !(DECL_ABSTRACT_ORIGIN (found)
 223            && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
 224     {
 225       DECL_NAME (result) = DECL_NAME (found);
 226       DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 227       DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 228     }
 229
 230   TREE_ADDRESSABLE (result) |= TREE_ADDRESSABLE (found);
 231
 232   /* Now walk through the function changing all references to VAR to be
 233      RESULT.  */
 234   data.var = found;
 235   data.result = result;
 236   FOR_EACH_BB (bb)
 237     {
 238       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 239         {
 240           gimple stmt = gsi_stmt (gsi);
 241           /* If this is a copy from VAR to RESULT, remove it.  */
 242           if (gimple_assign_copy_p (stmt)
 243               && gimple_assign_lhs (stmt) == result
 244               && gimple_assign_rhs1 (stmt) == found)
 245             {
 246               unlink_stmt_vdef (stmt);
 247               gsi_remove (&gsi, true);
 248             }
 249           else
 250             {
 251               struct walk_stmt_info wi;
 252               memset (&wi, 0, sizeof (wi));
 253               wi.info = &data;
 254               data.modified = 0;
 255               walk_gimple_op (stmt, finalize_nrv_r, &wi);
 256               if (data.modified)
 257                 update_stmt (stmt);
 258               gsi_next (&gsi);
 259             }
 260         }
 261     }
 262
 263   /* FOUND is no longer used.  Ensure it gets removed.  */
 264   var_ann (found)->used = 0;
 265   return 0;
 266 }
 267
 268 static bool
 269 gate_pass_return_slot (void)
 270 {
 271   return optimize > 0;
 272 }
 273
 274 struct gimple_opt_pass pass_nrv =
 275 {
 276  {
 277   GIMPLE_PASS,
 278   "nrv",                                /* name */
 279   gate_pass_return_slot,                /* gate */
 280   tree_nrv,                             /* execute */
 281   NULL,                                 /* sub */
 282   NULL,                                 /* next */
 283   0,                                    /* static_pass_number */
 284   TV_TREE_NRV,                          /* tv_id */
 285   PROP_ssa | PROP_cfg,                          /* properties_required */
 286   0,                                    /* properties_provided */
 287   0,                                    /* properties_destroyed */
 288   0,                                    /* todo_flags_start */
 289   TODO_dump_func | TODO_ggc_collect                     /* todo_flags_finish */
 290  }
 291 };
 292
 293 /* Determine (pessimistically) whether DEST is available for NRV
 294    optimization, where DEST is expected to be the LHS of a modify
 295    expression where the RHS is a function returning an aggregate.
 296
 297    DEST is available if it is not clobbered by the call.  */
 298
 299 static bool
 300 dest_safe_for_nrv_p (gimple call)
 301 {
 302   tree dest = gimple_call_lhs (call);
 303
 304   dest = get_base_address (dest);
 305   if (! dest)
 306     return false;
 307
 308   if (TREE_CODE (dest) == SSA_NAME)
 309     return true;
 310
 311   if (call_may_clobber_ref_p (call, dest))
 312     return false;
 313
 314   return true;
 315 }
 316
 317 /* Walk through the function looking for GIMPLE_ASSIGNs with calls that
 318    return in memory on the RHS.  For each of these, determine whether it is
 319    safe to pass the address of the LHS as the return slot, and mark the
 320    call appropriately if so.
 321
 322    The NRV shares the return slot with a local variable in the callee; this
 323    optimization shares the return slot with the target of the call within
 324    the caller.  If the NRV is performed (which we can't know in general),
 325    this optimization is safe if the address of the target has not
 326    escaped prior to the call.  If it has, modifications to the local
 327    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 328
 329 static unsigned int
 330 execute_return_slot_opt (void)
 331 {
 332   basic_block bb;
 333
 334   FOR_EACH_BB (bb)
 335     {
 336       gimple_stmt_iterator gsi;
 337       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 338         {
 339           gimple stmt = gsi_stmt (gsi);
 340           bool slot_opt_p;
 341
 342           if (is_gimple_call (stmt)
 343               && gimple_call_lhs (stmt)
 344               && !gimple_call_return_slot_opt_p (stmt)
 345               && aggregate_value_p (TREE_TYPE (gimple_call_lhs (stmt)),
 346                                     gimple_call_fndecl (stmt))
 347              )
 348             {
 349               /* Check if the location being assigned to is
 350                  clobbered by the call.  */
 351               slot_opt_p = dest_safe_for_nrv_p (stmt);
 352               gimple_call_set_return_slot_opt (stmt, slot_opt_p);
 353             }
 354         }
 355     }
 356   return 0;
 357 }
 358
 359 struct gimple_opt_pass pass_return_slot =
 360 {
 361  {
 362   GIMPLE_PASS,
 363   "retslot",                            /* name */
 364   NULL,                                 /* gate */
 365   execute_return_slot_opt,              /* execute */
 366   NULL,                                 /* sub */
 367   NULL,                                 /* next */
 368   0,                                    /* static_pass_number */
 369   TV_NONE,                              /* tv_id */
 370   PROP_ssa,                             /* properties_required */
 371   0,                                    /* properties_provided */
 372   0,                                    /* properties_destroyed */
 373   0,                                    /* todo_flags_start */
 374   0                                     /* todo_flags_finish */
 375  }
 376 };