This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa, C++] PATCH for optimization/11269: Reimplement namedreturn value optimization


My previous implementation of the NRVO worked (for non-inline functions) by
arranging for the RESULT_DECL to share RTL with a chosen local variable.
On the tree-ssa branch this has always been a bit dodgy, since anything
that relies on messing with RTL isn't likely to work properly.  PR 11269 is
an example of something that breaks as a result; the testcase
g++.dg/opt/nrv3.C has also been failing.

This patch changes the NRVO implementation to work by simply replacing all
uses of the chosen variable with the RESULT_DECL.  I had previously
discarded this idea when someone (Gaby?) suggested it, citing debugging
concerns, but the dwarf2out change ought to avoid any problems with
debugging.  There are no new failures in the gdb testsuite, at any rate.

The walk_tree and c_walk_subtrees changes are not necessary, but seem
reasonable.  It certainly doesn't make sense to walk into the
BIND_EXPR_VARS of a BIND_EXPR, since that would just give us the first
variable.  This is less clear for DECL_STMT, but there too I think that if
people want to mess with decls, their callback should massage the BIND_EXPR
or DECL_STMT, as finalize_nrv_r does below.

The mostly_copy_tree_r change is unrelated; it's a side-effect of my
earlier work on the Java unsharing bug.  If we try to copy a BLOCK we
really don't want to keep walking into its subtrees; we don't actually ever
copy a BLOCK, so copying its subtrees wouldn't do any good.

Tested athlon-pc-linux-gnu, applied to tree-ssa.

2003-11-16  Jason Merrill  <jason@redhat.com>

	PR optimization/11269
	* semantics.c (finalize_nrv_r): Rename from nullify_returns_r.
	Also replace uses of the nrv with our RESULT_DECL.
	(cxx_expand_function_start): Don't mess with the nrv.
	(finalize_nrv): New fn.
	* cp-tree.h: Declare it.
	* decl.c (finish_function): Call it.
	* tree.c (cp_copy_res_decl_for_inlining): Don't mess with the nrv.
	* dwarf2out.c (gen_subprogram_die): Generate a DIE for a named
	return value.
	(loc_descriptor_from_tree): Treat RESULT_DECL like VAR_DECL.
	(add_location_or_const_value_attribute): Likewise.
	(add_bound_info): Likewise.
	(gen_decl_die): Likewise.

	* tree-inline.c (walk_tree): Don't walk into the BIND_EXPR_VARS
	of a BIND_EXPR.
	* c-common.c (c_walk_subtrees): Don't walk into the decl of a
	DECL_STMT.

	* gimplify.c (mostly_copy_tree_r): Don't walk into a BLOCK.

*** cp/semantics.c.~1~	2003-11-15 16:26:51.000000000 -0500
--- cp/semantics.c	2003-11-16 01:38:30.000000000 -0500
*************** static void genrtl_try_block (tree);
*** 61,66 ****
--- 61,67 ----
  static void genrtl_eh_spec_block (tree);
  static void genrtl_handler (tree);
  static void cp_expand_stmt (tree);
+ static tree finalize_nrv_r (tree *, int *, void *);
  
  
  /* Finish processing the COND, the SUBSTMT condition for STMT.  */
*************** expand_or_defer_fn (tree fn)
*** 2968,3004 ****
    function_depth--;
  }
  
! /* Helper function for walk_tree, used by finish_function to override all
!    the RETURN_STMTs and pertinent CLEANUP_STMTs for the named return
!    value optimization.  */
  
! tree
! nullify_returns_r (tree* tp, int* walk_subtrees, void* data)
  {
!   tree nrv = (tree) data;
  
    /* No need to walk into types.  There wouldn't be any need to walk into
       non-statements, except that we have to consider STMT_EXPRs.  */
    if (TYPE_P (*tp))
      *walk_subtrees = 0;
    else if (TREE_CODE (*tp) == RETURN_STMT)
!     RETURN_STMT_EXPR (*tp) = NULL_TREE;
    else if (TREE_CODE (*tp) == CLEANUP_STMT
! 	   && CLEANUP_DECL (*tp) == nrv)
      CLEANUP_EH_ONLY (*tp) = 1;
  
    /* Keep iterating.  */
    return NULL_TREE;
  }
  
  /* Start generating the RTL for FN.  */
  
  void
  cxx_expand_function_start (void)
  {
-   /* Give our named return value the same RTL as our RESULT_DECL.  */
-   if (current_function_return_value)
-     COPY_DECL_RTL (DECL_RESULT (cfun->decl), current_function_return_value);
  }
  
  /* Perform initialization related to this module.  */
--- 2969,3069 ----
    function_depth--;
  }
  
! struct nrv_data
! {
!   tree var;
!   tree result;
!   htab_t visited;
! };
  
! /* Helper function for walk_tree, used by finalize_nrv below.  */
! 
! static tree
! finalize_nrv_r (tree* tp, int* walk_subtrees, void* data)
  {
!   struct nrv_data *dp = (struct nrv_data *)data;
!   void **slot;
  
    /* No need to walk into types.  There wouldn't be any need to walk into
       non-statements, except that we have to consider STMT_EXPRs.  */
    if (TYPE_P (*tp))
      *walk_subtrees = 0;
+   /* Change all returns to just refer to the RESULT_DECL; this is a nop,
+      but differs from using NULL_TREE in that it indicates that we care
+      about the value of the RESULT_DECL.  */
    else if (TREE_CODE (*tp) == RETURN_STMT)
!     RETURN_STMT_EXPR (*tp) = dp->result;
!   /* Change all cleanups for the NRV to only run when an exception is
!      thrown.  */
    else if (TREE_CODE (*tp) == CLEANUP_STMT
! 	   && CLEANUP_DECL (*tp) == dp->var)
      CLEANUP_EH_ONLY (*tp) = 1;
+   /* Replace the DECL_STMT for the NRV with an initialization of the
+      RESULT_DECL, if needed.  */
+   else if (TREE_CODE (*tp) == DECL_STMT
+ 	   && DECL_STMT_DECL (*tp) == dp->var)
+     {
+       tree init;
+       if (DECL_INITIAL (dp->var)
+ 	  && DECL_INITIAL (dp->var) != error_mark_node)
+ 	{
+ 	  init = build (INIT_EXPR, void_type_node, dp->result,
+ 			DECL_INITIAL (dp->var));
+ 	  DECL_INITIAL (dp->var) = error_mark_node;
+ 	}
+       else
+ 	init = NULL_TREE;
+       init = build_stmt (EXPR_STMT, init);
+       STMT_LINENO (init) = STMT_LINENO (*tp);
+       TREE_CHAIN (init) = TREE_CHAIN (*tp);
+       *tp = init;
+     }
+   /* And replace all uses of the NRV with the RESULT_DECL.  */
+   else if (*tp == dp->var)
+     *tp = dp->result;
+ 
+   /* Avoid walking into the same tree more than once.  Unfortunately, we
+      can't just use walk_tree_without duplicates because it would only call
+      us for the first occurrence of dp->var in the function body.  */
+   slot = htab_find_slot (dp->visited, *tp, INSERT);
+   if (*slot)
+     *walk_subtrees = 0;
+   else
+     *slot = *tp;
  
    /* Keep iterating.  */
    return NULL_TREE;
  }
  
+ /* Called from finish_function to implement the named return value
+    optimization by overriding all the RETURN_STMTs and pertinent
+    CLEANUP_STMTs and replacing all occurrences of VAR with RESULT, the
+    RESULT_DECL for the function.  */
+ 
+ void
+ finalize_nrv (tree *tp, tree var, tree result)
+ {
+   struct nrv_data data;
+ 
+   /* Copy debugging information from VAR to RESULT.  */
+   DECL_NAME (result) = DECL_NAME (var);
+   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (var);
+   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (var);
+   /* Don't forget that we take its address.  */
+   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (var);
+ 
+   data.var = var;
+   data.result = result;
+   data.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+   walk_tree (tp, finalize_nrv_r, &data, 0);
+   htab_delete (data.visited);
+ }
+ 
  /* Start generating the RTL for FN.  */
  
  void
  cxx_expand_function_start (void)
  {
  }
  
  /* Perform initialization related to this module.  */
*** cp/decl.c.~1~	2003-11-15 16:26:51.000000000 -0500
--- cp/decl.c	2003-11-15 15:00:56.000000000 -0500
*************** finish_function (int flags)
*** 10743,10752 ****
       of curly braces for a function.  */
    my_friendly_assert (stmts_are_full_exprs_p (), 19990831);
  
!   /* Set up the named return value optimization, if we can.  Here, we
!      eliminate the copy from the nrv into the RESULT_DECL and any cleanup
!      for the nrv.  genrtl_start_function and declare_return_variable
!      handle making the nrv and RESULT_DECL share space.  */
    if (current_function_return_value)
      {
        tree r = current_function_return_value;
--- 10743,10750 ----
       of curly braces for a function.  */
    my_friendly_assert (stmts_are_full_exprs_p (), 19990831);
  
!   /* Set up the named return value optimization, if we can.  Candidate
!      variables are selected in check_return_value.  */
    if (current_function_return_value)
      {
        tree r = current_function_return_value;
*************** finish_function (int flags)
*** 10763,10778 ****
  	  /* Skip the artificial function body block.  */
  	  && (outer = BLOCK_SUBBLOCKS (BLOCK_SUBBLOCKS (DECL_INITIAL (fndecl))),
  	      chain_member (r, BLOCK_VARS (outer))))
! 	{
! 	  set_has_hidden_use (r);
! 	  DECL_ALIGN (r) = DECL_ALIGN (DECL_RESULT (fndecl));
! 	  walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
! 					nullify_returns_r, r);
! 	}
!       else
! 	/* Clear it so genrtl_start_function and declare_return_variable
! 	   know we're not optimizing.  */
! 	current_function_return_value = NULL_TREE;
      }
  
    /* Remember that we were in class scope.  */
--- 10761,10769 ----
  	  /* Skip the artificial function body block.  */
  	  && (outer = BLOCK_SUBBLOCKS (BLOCK_SUBBLOCKS (DECL_INITIAL (fndecl))),
  	      chain_member (r, BLOCK_VARS (outer))))
! 	finalize_nrv (&DECL_SAVED_TREE (fndecl), r, DECL_RESULT (fndecl));
! 
!       current_function_return_value = NULL_TREE;
      }
  
    /* Remember that we were in class scope.  */
*** cp/tree.c.~1~	2003-11-15 16:26:51.000000000 -0500
--- cp/tree.c	2003-11-14 16:20:37.000000000 -0500
*************** tree
*** 2117,2127 ****
  cp_copy_res_decl_for_inlining (tree result, 
                                 tree fn, 
                                 tree caller, 
!                                void* decl_map_,
                                 int* need_decl, 
                                 tree return_slot_addr)
  {
-   splay_tree decl_map = (splay_tree)decl_map_;
    tree var;
  
    /* If FN returns an aggregate then the caller will always pass the
--- 2117,2126 ----
  cp_copy_res_decl_for_inlining (tree result, 
                                 tree fn, 
                                 tree caller, 
!                                void* decl_map_ ATTRIBUTE_UNUSED,
                                 int* need_decl, 
                                 tree return_slot_addr)
  {
    tree var;
  
    /* If FN returns an aggregate then the caller will always pass the
*************** cp_copy_res_decl_for_inlining (tree resu
*** 2149,2182 ****
    else
      var = copy_decl_for_inlining (result, fn, caller);
  
-   if (DECL_SAVED_FUNCTION_DATA (fn))
-     {
-       tree nrv = DECL_SAVED_FUNCTION_DATA (fn)->x_return_value;
-       if (nrv)
- 	{
- 	  /* We have a named return value; copy the name and source
- 	     position so we can get reasonable debugging information, and
- 	     register the return variable as its equivalent.  */
- 	  if (TREE_CODE (var) == VAR_DECL
- 	      /* But not if we're initializing a variable from the
- 		 enclosing function which already has its own name.  */
- 	      && DECL_NAME (var) == NULL_TREE)
- 	    {
- 	      DECL_NAME (var) = DECL_NAME (nrv);
- 	      DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (nrv);
- 	      DECL_ABSTRACT_ORIGIN (var) = DECL_ORIGIN (nrv);
- 	      /* Don't lose initialization info.  */
- 	      DECL_INITIAL (var) = DECL_INITIAL (nrv);
- 	      /* Don't forget that it needs to go in the stack.  */
- 	      TREE_ADDRESSABLE (var) = TREE_ADDRESSABLE (nrv);
- 	    }
- 
- 	  splay_tree_insert (decl_map,
- 			     (splay_tree_key) nrv,
- 			     (splay_tree_value) var);
- 	}
-     }
- 
    return var;
  }
  
--- 2148,2153 ----
*** cp/cp-tree.h.~1~	2003-11-15 16:26:51.000000000 -0500
--- cp/cp-tree.h	2003-11-15 14:48:00.000000000 -0500
*************** extern void finish_decl_cleanup         
*** 4074,4080 ****
  extern void finish_eh_cleanup                   (tree);
  extern void expand_body                         (tree);
  extern void cxx_expand_function_start		(void);
- extern tree nullify_returns_r		      (tree *, int *, void *);
  extern void do_pushlevel                        (scope_kind);
  extern tree do_poplevel                         (void);
  extern void finish_mem_initializers             (tree);
--- 4074,4079 ----
*************** extern void expand_or_defer_fn			(tree);
*** 4085,4090 ****
--- 4084,4090 ----
  extern void check_accessibility_of_qualified_id (tree, tree, tree);
  extern tree finish_qualified_id_expr            (tree, tree, bool, bool);
  extern void simplify_aggr_init_expr		(tree *);
+ extern void finalize_nrv			(tree *, tree, tree);
  
  /* in tree.c */
  extern void lang_check_failed			(const char *, int,
*** dwarf2out.c.~1~	2003-11-10 18:55:53.000000000 -0500
--- dwarf2out.c	2003-11-16 19:02:39.000000000 -0500
*************** loc_descriptor_from_tree (tree loc, int 
*** 8488,8493 ****
--- 8488,8494 ----
        /* FALLTHRU */
  
      case PARM_DECL:
+     case RESULT_DECL:
        {
  	rtx rtl = rtl_for_decl_location (loc);
  
*************** add_location_or_const_value_attribute (d
*** 9400,9406 ****
  
    if (TREE_CODE (decl) == ERROR_MARK)
      return;
!   else if (TREE_CODE (decl) != VAR_DECL && TREE_CODE (decl) != PARM_DECL)
      abort ();
  
    rtl = rtl_for_decl_location (decl);
--- 9401,9408 ----
  
    if (TREE_CODE (decl) == ERROR_MARK)
      return;
!   else if (TREE_CODE (decl) != VAR_DECL && TREE_CODE (decl) != PARM_DECL
! 	   && TREE_CODE (decl) != RESULT_DECL)
      abort ();
  
    rtl = rtl_for_decl_location (decl);
*************** add_bound_info (dw_die_ref subrange_die,
*** 9588,9593 ****
--- 9590,9596 ----
  
      case VAR_DECL:
      case PARM_DECL:
+     case RESULT_DECL:
        {
  	dw_die_ref decl_die = lookup_decl_die (bound);
  
*************** gen_subprogram_die (tree decl, dw_die_re
*** 10807,10812 ****
--- 10810,10819 ----
       constructor function.  */
    if (! declaration && TREE_CODE (outer_scope) != ERROR_MARK)
      {
+       /* Emit a DW_TAG_variable DIE for a named return value.  */
+       if (DECL_NAME (DECL_RESULT (decl)))
+ 	gen_decl_die (DECL_RESULT (decl), subr_die);
+ 
        current_function_has_inlines = 0;
        decls_for_scope (outer_scope, subr_die, 0);
  
*************** gen_decl_die (tree decl, dw_die_ref cont
*** 11871,11876 ****
--- 11878,11884 ----
        break;
  
      case VAR_DECL:
+     case RESULT_DECL:
        /* If we are in terse mode, don't generate any DIEs to represent any
  	 variable declarations or definitions.  */
        if (debug_info_level <= DINFO_LEVEL_TERSE)
*** tree-inline.c.~1~	2003-11-15 16:26:03.000000000 -0500
--- tree-inline.c	2003-11-15 16:30:50.000000000 -0500
*************** walk_tree (tree *tp, walk_tree_fn func, 
*** 1855,1860 ****
--- 1855,1861 ----
  
    if (code != EXIT_BLOCK_EXPR
        && code != SAVE_EXPR
+       && code != BIND_EXPR
        && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
      {
        int i, len;
*************** walk_tree (tree *tp, walk_tree_fn func, 
*** 1868,1873 ****
--- 1869,1878 ----
  	--len;
        /* Go through the subtrees.  We need to do this in forward order so
           that the scope of a FOR_EXPR is handled properly.  */
+ #ifdef DEBUG_WALK_TREE
+       for (i = 0; i < len; ++i)
+ 	WALK_SUBTREE (TREE_OPERAND (*tp, i));
+ #else
        for (i = 0; i < len - 1; ++i)
  	WALK_SUBTREE (TREE_OPERAND (*tp, i));
  
*************** walk_tree (tree *tp, walk_tree_fn func, 
*** 1880,1902 ****
  	  else
  	    WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
  	}
! 
!       if (code == BIND_EXPR)
! 	{
! 	  tree decl;
! 	  for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
! 	    {
! 	      /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
! 		 into declarations that are just mentioned, rather than
! 		 declared; they don't really belong to this part of the tree.
! 		 And, we can see cycles: the initializer for a declaration can
! 		 refer to the declaration itself.  */
! 	      WALK_SUBTREE (DECL_INITIAL (decl));
! 	      WALK_SUBTREE (DECL_SIZE (decl));
! 	      WALK_SUBTREE (DECL_SIZE_UNIT (decl));
! 	      WALK_SUBTREE (TREE_TYPE (decl));
! 	    }
! 	}
  
        if ((*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
  	/* Check our siblings.  */
--- 1885,1891 ----
  	  else
  	    WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
  	}
! #endif
  
        if ((*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
  	/* Check our siblings.  */
*************** walk_tree (tree *tp, walk_tree_fn func, 
*** 2006,2011 ****
--- 1995,2018 ----
  	case SAVE_EXPR:
  	  WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
  
+ 	case BIND_EXPR:
+ 	  {
+ 	    tree decl;
+ 	    for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
+ 	      {
+ 		/* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
+ 		   into declarations that are just mentioned, rather than
+ 		   declared; they don't really belong to this part of the tree.
+ 		   And, we can see cycles: the initializer for a declaration can
+ 		   refer to the declaration itself.  */
+ 		WALK_SUBTREE (DECL_INITIAL (decl));
+ 		WALK_SUBTREE (DECL_SIZE (decl));
+ 		WALK_SUBTREE (DECL_SIZE_UNIT (decl));
+ 		WALK_SUBTREE (TREE_TYPE (decl));
+ 	      }
+ 	    WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
+ 	  }
+ 
  	case STATEMENT_LIST:
  	  {
  	    tree_stmt_iterator i;
*** c-common.c.~1~	2003-11-15 16:26:03.000000000 -0500
--- c-common.c	2003-11-15 16:20:12.000000000 -0500
*************** c_walk_subtrees (tree *tp, int *walk_sub
*** 5844,5849 ****
--- 5844,5851 ----
        WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
        WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
        WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
+       WALK_SUBTREE (TREE_CHAIN (*tp));
+       *walk_subtrees_p = 0;
      }
  
    /* We didn't find what we were looking for.  */
*** gimplify.c.~1~	2003-11-15 16:22:17.000000000 -0500
--- gimplify.c	2003-11-15 16:30:50.000000000 -0500
*************** mostly_copy_tree_r (tree *tp, int *walk_
*** 594,600 ****
    /* Don't unshare types, constants and SAVE_EXPR nodes.  */
    if (TREE_CODE_CLASS (code) == 't'
        || TREE_CODE_CLASS (code) == 'c'
!       || code == SAVE_EXPR)
      *walk_subtrees = 0;
    else if (code == BIND_EXPR)
      abort ();
--- 594,604 ----
    /* Don't unshare types, constants and SAVE_EXPR nodes.  */
    if (TREE_CODE_CLASS (code) == 't'
        || TREE_CODE_CLASS (code) == 'c'
!       || code == SAVE_EXPR
!       /* We can't do anything sensible with a BLOCK used as an expression,
! 	 but we also can't abort when we see it because of non-expression
! 	 uses.  So just avert our eyes and cross our fingers.  Silly Java.  */
!       || code == BLOCK)
      *walk_subtrees = 0;
    else if (code == BIND_EXPR)
      abort ();

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]