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