gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004 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 2, 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 COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "function.h"
  28 #include "basic-block.h"
  29 #include "expr.h"
  30 #include "diagnostic.h"
  31 #include "tree-flow.h"
  32 #include "timevar.h"
  33 #include "tree-dump.h"
  34 #include "tree-pass.h"
  35 #include "langhooks.h"
  36
  37 /* This file implements return value optimizations for functions which
  38    return aggregate types.
  39
  40    Basically this pass searches the function for return statements which
  41    return a local aggregate.  When converted to RTL such statements will
  42    generate a copy from the local aggregate to final return value destination
  43    mandated by the target's ABI.
  44
  45    That copy can often be avoided by directly constructing the return value
  46    into the final destination mandated by the target's ABI.
  47
  48    This is basically a generic equivalent to the C++ front-end's
  49    Named Return Value optimization.  */
  50
  51 struct nrv_data
  52 {
  53   /* This is the temporary (a VAR_DECL) which appears in all of
  54      this function's RETURN_EXPR statements.  */
  55   tree var;
  56
  57   /* This is the function's RESULT_DECL.  We will replace all occurences
  58      of VAR with RESULT_DECL when we apply this optimization.  */
  59   tree result;
  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 nrv_data *dp = (struct nrv_data *)data;
  79
  80   /* No need to walk into types.  */
  81   if (TYPE_P (*tp))
  82     *walk_subtrees = 0;
  83   /* If this is a RETURN_EXPR, then set the expression being returned
  84      to RESULT.  */
  85   else if (TREE_CODE (*tp) == RETURN_EXPR)
  86     TREE_OPERAND (*tp, 0) = dp->result;
  87   /* Replace all occurences of VAR with RESULT.  */
  88   else if (*tp == dp->var)
  89     *tp = dp->result;
  90
  91   /* Keep iterating.  */
  92   return NULL_TREE;
  93 }
  94
  95 /* Main entry point for return value optimizations.
  96
  97    If this function always returns the same local variable, and that
  98    local variable is an aggregate type, then replace the variable with
  99    the function's DECL_RESULT.
 100
 101    This is the equivalent of the C++ named return value optimization
 102    applied to optimized trees in a language independent form.  If we
 103    ever encounter languages which prevent this kind of optimization,
 104    then we could either have the languages register the optimization or
 105    we could change the gating function to check the current language.  */
 106
 107 static void
 108 tree_nrv (void)
 109 {
 110   tree result = DECL_RESULT (current_function_decl);
 111   tree result_type = TREE_TYPE (result);
 112   tree found = NULL;
 113   basic_block bb;
 114   struct nrv_data data;
 115
 116   /* If this function does not return an aggregate type in memory, then
 117      there is nothing to do.  */
 118   if (!aggregate_value_p (result, current_function_decl))
 119     return;
 120
 121   /* Look through each block for suitable return expressions.   RETURN_EXPRs
 122      end basic blocks, so we only have to look at the last statement in
 123      each block.  That makes this very fast.  */
 124   FOR_EACH_BB (bb)
 125     {
 126       tree stmt = last_stmt (bb);
 127
 128       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
 129         {
 130           tree ret_expr = TREE_OPERAND (stmt, 0);
 131
 132           /* This probably should not happen, but just to be safe do
 133              not perform NRV optimizations if only some of the return
 134              statement return a value.  */
 135           if (!ret_expr
 136               || TREE_CODE (ret_expr) != MODIFY_EXPR
 137               || TREE_CODE (TREE_OPERAND (ret_expr, 0)) != RESULT_DECL)
 138             return;
 139
 140           /* Now verify that this return statement uses the same value
 141              as any previously encountered return statement.  */
 142           if (found != NULL)
 143             {
 144               /* If we found a return statement using a different variable
 145                  than previous return statements, then we can not perform
 146                  NRV optimizations.  */
 147               if (found != TREE_OPERAND (ret_expr, 1))
 148                 return;
 149             }
 150           else
 151             found = TREE_OPERAND (ret_expr, 1);
 152
 153           /* The returned value must be a local automatic variable of the
 154              same type and alignment as the function's result.  */
 155           if (TREE_CODE (found) != VAR_DECL
 156               || DECL_CONTEXT (found) != current_function_decl
 157               || TREE_STATIC (found)
 158               || TREE_ADDRESSABLE (found)
 159               || DECL_ALIGN (found) > DECL_ALIGN (result)
 160               || !lang_hooks.types_compatible_p (TREE_TYPE (found),
 161                  result_type))
 162             return;
 163         }
 164     }
 165
 166   if (!found)
 167     return;
 168
 169   /* If dumping details, then note once and only the NRV replacement.  */
 170   if (dump_file && (dump_flags & TDF_DETAILS))
 171     {
 172       fprintf (dump_file, "NRV Replaced: ");
 173       print_generic_expr (dump_file, found, dump_flags);
 174       fprintf (dump_file, "  with: ");
 175       print_generic_expr (dump_file, result, dump_flags);
 176       fprintf (dump_file, "\n");
 177     }
 178
 179   /* At this point we know that all the return statements return the
 180      same local which has suitable attributes for NRV.   Copy debugging
 181      information from FOUND to RESULT.  */
 182   DECL_NAME (result) = DECL_NAME (found);
 183   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 184   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 185   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 186
 187   /* Now walk through the function changing all references to VAR to be
 188      RESULT.  */
 189   data.var = found;
 190   data.result = result;
 191   FOR_EACH_BB (bb)
 192     {
 193       block_stmt_iterator bsi;
 194
 195       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 196         walk_tree (bsi_stmt_ptr (bsi), finalize_nrv_r, &data, 0);
 197     }
 198
 199   /* FOUND is no longer used.  Ensure it gets removed.  */
 200   var_ann (found)->used = 0;
 201 }
 202
 203 struct tree_opt_pass pass_nrv =
 204 {
 205   "nrv",                                /* name */
 206   NULL,                                 /* gate */
 207   tree_nrv,                             /* execute */
 208   NULL,                                 /* sub */
 209   NULL,                                 /* next */
 210   0,                                    /* static_pass_number */
 211   TV_TREE_NRV,                          /* tv_id */
 212   PROP_cfg,                             /* properties_required */
 213   0,                                    /* properties_provided */
 214   0,                                    /* properties_destroyed */
 215   0,                                    /* todo_flags_start */
 216   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 217 };