PATCH: RTL_EXPR vs. inlining-on-trees

Mark Mitchell mark@codesourcery.com
Sat Mar 4 17:58:00 GMT 2000


Here's a fix for a tree-based inlining bug that Gerald found.

The fix consists entirely of removing code.

The RTL_EXPR tree node allows one to embed a section of RTL in a tree.
The semantics of such are thing are that when the RTL_EXPR is
encountered, it is expanded into the instruction stream.
Unfortunately, these nodes had a second, uncodumented semantic
property: any stack slots allocated during the creation of the
RTL_EXPR were freed, as if the RTL_EXPR defined a scope.  In other
words, there was no way to define an RTL_EXPR for something like:

  int i;
  i = 3;

instead, you got:

  { int i; i = 3; }

That's a unfortunate non-orthogonality.  

Additionally, the potential win here is small.  In C, RTL_EXPRs occur
when statement-expressions are used.  So, a stack slot can be reused
before the end of the scope containing the statement-expression.

Although that's a win, it doesn't impress me much.  Our stack-slot
allocation code is lousy as it is -- what's really needed is something
like register allocation, where we get lots of stack-slot pseudos, and
the actual slot is chosen later, based on a coloring of which stack
slots are simultaneously live.  Presently, with heavy optimizations on
big functions, we end up with stack frames of up to 100K, often with
as little as 1K actually used.

In C++, we use statement-expressions to represent tree-based inlining.
We'll do that in C, too, one of these days.  Here, the implicit scope
is undesirable.

So, rather than add a flag to the RTL_EXPR, allowing front-ends to
indicate whether or not the RTL_EXPR should define a scope, I've opted
simply to remove the ability for an RTL_EXPR to define a scope
altogether.  This removes one nasty bit of non-orthogonal complexity
whose potential for confusion is high, whose payoff is minor, and
whose benefits can be won back in the future via better optimization.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

2000-03-04  Mark Mitchell  <mark@codesourcery.com>

	* function.h (struct sequence_stack): Remove rtl_expr.
	(struct emit_staus): Likewise.
	(seq_rtl_expr): Remove.
	* tree.h (free_temps_for_rtl_expr): Don't declare.
	(start_sequence_for_rtl_expr): Likewise.
	* rtl.h (preserve_rtl_expr_result): Likewise.
	* emit-rtl.c (start_sequence): Don't set sequence_rtl_expr.
	(start_sequence_for_rtl_expr): Remove.
	(push_topmost_sequence): Don't save sequence_rtl_expr.
	(pop_topmost_sequence): Remove comment about not restoring it.
	(end_sequence): Don't set seq_rtl_expr.
	(init_emit): Don't initialize it.
	(mark_sequence_stack): Don't mark it.
	(mark_emit_status): Likewise.
	* except.c (protect_with_terminate): Use
	start_sequence_for_rtl_expr, not start_sequence.
	* expr.c (expand_expr, case RTL_EXPR): Don't call
	preserve_rtl_expr_result or free_temps_for_rtl_expr.
	(assign_stack_temp_for_type): Don't set rtl_expr.
	(preserve_rtl_expr_result): Remove.
	(free_temps_for_rtl_expr): Likewise.
	(pop_temp_slots): Likewise.
	(mark_temp_slot): Don't mark the rtl_expr.
	* stmt.c (expand_start_stmt_expr): Use start_sequence, not
	start_sequence_for_rtl_expr.
	
Index: testsuite/g++.old-deja/g++.other/inline8.C
===================================================================
RCS file: inline8.C
diff -N inline8.C
*** /dev/null	Tue May  5 13:32:27 1998
--- inline8.C	Sat Mar  4 17:28:34 2000
***************
*** 0 ****
--- 1,65 ----
+ // Origin: Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>
+ // Special g++ Options: -O1
+ 
+ #include <map>
+ #include <cstdlib>
+ 
+ class NAMES_ITEM
+     {
+ public:
+     char *name;
+ 
+       NAMES_ITEM(const NAMES_ITEM& item2);
+ 
+       NAMES_ITEM(const char* name2);
+ 
+       ~NAMES_ITEM();
+ 
+       bool operator==(const NAMES_ITEM& n) const;
+     };
+ 
+ 
+ NAMES_ITEM::NAMES_ITEM (const NAMES_ITEM& item2)
+         {
+         size_t length=strlen(item2.name);
+ 
+         name=new char[length+1];
+         memcpy(name,item2.name,length+1);
+         }
+ 
+ NAMES_ITEM::NAMES_ITEM (const char* name2)      
+         {
+         size_t length=strlen(name2);
+ 
+         name=new char[length+1];
+         memcpy(name,name2,length+1);
+         }
+ 
+ NAMES_ITEM::~NAMES_ITEM ()
+ {
+   if (strcmp (name, "one") != 0)
+     abort ();
+   
+   name=0;
+ }
+ 
+ bool NAMES_ITEM::operator==(const NAMES_ITEM& n) const
+ {
+   return (strcmp(name,n.name) == 0);
+ }
+ 
+ bool operator<(const NAMES_ITEM& n1, const NAMES_ITEM& n2)
+     {
+     return (strcmp(n1.name,n2.name) < 0);
+     }
+ 
+     typedef map<NAMES_ITEM,size_t,less<NAMES_ITEM> > lookup_t;
+ 
+     lookup_t lookup;
+ 
+ 	NAMES_ITEM item ("one");
+ main()
+   {
+         lookup.insert(pair<NAMES_ITEM,size_t>(item,0));
+   }
+ 
Index: emit-rtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/emit-rtl.c,v
retrieving revision 1.113
diff -c -p -r1.113 emit-rtl.c
*** emit-rtl.c	2000/03/04 09:32:34	1.113
--- emit-rtl.c	2000/03/05 00:41:10
*************** start_sequence ()
*** 3376,3382 ****
    tem->next = seq_stack;
    tem->first = first_insn;
    tem->last = last_insn;
-   tem->sequence_rtl_expr = seq_rtl_expr;
  
    seq_stack = tem;
  
--- 3376,3381 ----
*************** start_sequence ()
*** 3384,3402 ****
    last_insn = 0;
  }
  
- /* Similarly, but indicate that this sequence will be placed in T, an
-    RTL_EXPR.  See the documentation for start_sequence for more
-    information about how to use this function.  */
- 
- void
- start_sequence_for_rtl_expr (t)
-      tree t;
- {
-   start_sequence ();
- 
-   seq_rtl_expr = t;
- }
- 
  /* Set up the insn chain starting with FIRST as the current sequence,
     saving the previously current one.  See the documentation for
     start_sequence for more information about how to use this function.  */
--- 3383,3388 ----
*************** push_topmost_sequence ()
*** 3430,3436 ****
  
    first_insn = top->first;
    last_insn = top->last;
-   seq_rtl_expr = top->sequence_rtl_expr;
  }
  
  /* After emitting to the outer-level insn chain, update the outer-level
--- 3416,3421 ----
*************** pop_topmost_sequence ()
*** 3446,3452 ****
  
    top->first = first_insn;
    top->last = last_insn;
-   /* ??? Why don't we save seq_rtl_expr here?  */
  
    end_sequence ();
  }
--- 3431,3436 ----
*************** end_sequence ()
*** 3471,3477 ****
  
    first_insn = tem->first;
    last_insn = tem->last;
-   seq_rtl_expr = tem->sequence_rtl_expr;
    seq_stack = tem->next;
  
    free (tem);
--- 3455,3460 ----
*************** init_emit ()
*** 3760,3766 ****
    f->emit = (struct emit_status *) xmalloc (sizeof (struct emit_status));
    first_insn = NULL;
    last_insn = NULL;
-   seq_rtl_expr = NULL;
    cur_insn_uid = 1;
    reg_rtx_no = LAST_VIRTUAL_REGISTER + 1;
    last_linenum = 0;
--- 3743,3748 ----
*************** mark_sequence_stack (ss)
*** 3834,3840 ****
    while (ss)
      {
        ggc_mark_rtx (ss->first);
-       ggc_mark_tree (ss->sequence_rtl_expr);
        ss = ss->next;
      }
  }
--- 3816,3821 ----
*************** mark_emit_status (es)
*** 3856,3862 ****
      ggc_mark_rtx (*r);
  
    mark_sequence_stack (es->sequence_stack);
-   ggc_mark_tree (es->sequence_rtl_expr);
    ggc_mark_rtx (es->x_first_insn);
  }
  
--- 3837,3842 ----
Index: except.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/except.c,v
retrieving revision 1.116
diff -c -p -r1.116 except.c
*** except.c	2000/02/26 06:04:48	1.116
--- except.c	2000/03/05 00:41:12
*************** protect_with_terminate (e)
*** 2095,2101 ****
        TREE_TYPE (handler) = void_type_node;
        RTL_EXPR_RTL (handler) = const0_rtx;
        TREE_SIDE_EFFECTS (handler) = 1;
!       start_sequence_for_rtl_expr (handler);
  
        emit_library_call (terminate_libfunc, 0, VOIDmode, 0);
        emit_barrier ();
--- 2095,2101 ----
        TREE_TYPE (handler) = void_type_node;
        RTL_EXPR_RTL (handler) = const0_rtx;
        TREE_SIDE_EFFECTS (handler) = 1;
!       start_sequence ();
  
        emit_library_call (terminate_libfunc, 0, VOIDmode, 0);
        emit_barrier ();
Index: expr.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/expr.c,v
retrieving revision 1.205
diff -c -p -r1.205 expr.c
*** expr.c	2000/03/03 20:40:54	1.205
--- expr.c	2000/03/05 00:41:18
*************** expand_expr (exp, target, tmode, modifie
*** 6306,6313 ****
  	  emit_insns (RTL_EXPR_SEQUENCE (exp));
  	  RTL_EXPR_SEQUENCE (exp) = const0_rtx;
  	}
-       preserve_rtl_expr_result (RTL_EXPR_RTL (exp));
-       free_temps_for_rtl_expr (exp);
        return RTL_EXPR_RTL (exp);
  
      case CONSTRUCTOR:
--- 6306,6311 ----
Index: function.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/function.c,v
retrieving revision 1.168
diff -c -p -r1.168 function.c
*** function.c	2000/02/28 12:41:36	1.168
--- function.c	2000/03/05 00:41:22
*************** assign_stack_temp_for_type (mode, size, 
*** 708,714 ****
  						    rounded_size));
  	      p->align = best_p->align;
  	      p->address = 0;
- 	      p->rtl_expr = 0;
  	      p->next = temp_slots;
  	      temp_slots = p;
  
--- 708,713 ----
*************** assign_stack_temp_for_type (mode, size, 
*** 776,782 ****
  
    p->in_use = 1;
    p->addr_taken = 0;
-   p->rtl_expr = seq_rtl_expr;
  
    if (keep == 2)
      {
--- 775,780 ----
*************** preserve_temp_slots (x)
*** 1129,1162 ****
        p->level--;
  }
  
- /* X is the result of an RTL_EXPR.  If it is a temporary slot associated
-    with that RTL_EXPR, promote it into a temporary slot at the present
-    level so it will not be freed when we free slots made in the
-    RTL_EXPR.  */
- 
- void
- preserve_rtl_expr_result (x)
-      rtx x;
- {
-   struct temp_slot *p;
- 
-   /* If X is not in memory or is at a constant address, it cannot be in
-      a temporary slot.  */
-   if (x == 0 || GET_CODE (x) != MEM || CONSTANT_P (XEXP (x, 0)))
-     return;
- 
-   /* If we can find a match, move it to our level unless it is already at
-      an upper level.  */
-   p = find_temp_slot_from_address (XEXP (x, 0));
-   if (p != 0)
-     {
-       p->level = MIN (p->level, temp_slot_level);
-       p->rtl_expr = 0;
-     }
- 
-   return;
- }
- 
  /* Free all temporaries used so far.  This is normally called at the end
     of generating code for a statement.  Don't free any temporaries
     currently in use for an RTL_EXPR that hasn't yet been emitted.
--- 1127,1132 ----
*************** free_temp_slots ()
*** 1169,1192 ****
  {
    struct temp_slot *p;
  
-   for (p = temp_slots; p; p = p->next)
-     if (p->in_use && p->level == temp_slot_level && ! p->keep
- 	&& p->rtl_expr == 0)
-       p->in_use = 0;
- 
-   combine_temp_slots ();
- }
- 
- /* Free all temporary slots used in T, an RTL_EXPR node.  */
- 
- void
- free_temps_for_rtl_expr (t)
-      tree t;
- {
-   struct temp_slot *p;
- 
    for (p = temp_slots; p; p = p->next)
!     if (p->rtl_expr == t)
        p->in_use = 0;
  
    combine_temp_slots ();
--- 1139,1146 ----
  {
    struct temp_slot *p;
  
    for (p = temp_slots; p; p = p->next)
!     if (p->in_use && p->level == temp_slot_level && ! p->keep)
        p->in_use = 0;
  
    combine_temp_slots ();
*************** pop_temp_slots ()
*** 1264,1270 ****
    struct temp_slot *p;
  
    for (p = temp_slots; p; p = p->next)
!     if (p->in_use && p->level == temp_slot_level && p->rtl_expr == 0)
        p->in_use = 0;
  
    combine_temp_slots ();
--- 1218,1224 ----
    struct temp_slot *p;
  
    for (p = temp_slots; p; p = p->next)
!     if (p->in_use && p->level == temp_slot_level)
        p->in_use = 0;
  
    combine_temp_slots ();
*************** mark_temp_slot (t)
*** 6980,6987 ****
      {
        ggc_mark_rtx (t->slot);
        ggc_mark_rtx (t->address);
-       ggc_mark_tree (t->rtl_expr);
- 
        t = t->next;
      }
  }
--- 6934,6939 ----
Index: function.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/function.h,v
retrieving revision 1.47
diff -c -p -r1.47 function.h
*** function.h	2000/03/02 23:50:10	1.47
--- function.h	2000/03/05 00:41:23
*************** struct sequence_stack
*** 46,52 ****
  {
    /* First and last insns in the chain of the saved sequence.  */
    rtx first, last;
-   tree sequence_rtl_expr;
    struct sequence_stack *next;
  };
  
--- 46,51 ----
*************** struct emit_status
*** 77,87 ****
    rtx x_first_insn;
    rtx x_last_insn;
  
-   /* RTL_EXPR within which the current sequence will be placed.  Use to
-      prevent reuse of any temporaries within the sequence until after the
-      RTL_EXPR is emitted.  */
-   tree sequence_rtl_expr;
- 
    /* Stack of pending (incomplete) sequences saved by `start_sequence'.
       Each element describes one pending sequence.
       The main insn-chain is saved in the last element of the chain,
--- 76,81 ----
*************** struct emit_status
*** 117,123 ****
  
  /* For backward compatibility... eventually these should all go away.  */
  #define reg_rtx_no (cfun->emit->x_reg_rtx_no)
- #define seq_rtl_expr (cfun->emit->sequence_rtl_expr)
  #define regno_reg_rtx (cfun->emit->x_regno_reg_rtx)
  #define seq_stack (cfun->emit->sequence_stack)
  
--- 111,116 ----
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.h,v
retrieving revision 1.171
diff -c -p -r1.171 rtl.h
*** rtl.h	2000/02/28 12:08:41	1.171
--- rtl.h	2000/03/05 00:41:25
*************** extern void reposition_prologue_and_epil
*** 1508,1514 ****
  extern void thread_prologue_and_epilogue_insns		PARAMS ((rtx));
  extern int prologue_epilogue_contains			PARAMS ((rtx));
  extern HOST_WIDE_INT get_frame_size			PARAMS ((void));
- extern void preserve_rtl_expr_result			PARAMS ((rtx));
  extern void mark_temp_addr_taken			PARAMS ((rtx));
  extern void update_temp_slot_address			PARAMS ((rtx, rtx));
  extern void purge_addressof				PARAMS ((rtx));
--- 1508,1513 ----
Index: stmt.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/stmt.c,v
retrieving revision 1.125
diff -c -p -r1.125 stmt.c
*** stmt.c	2000/03/04 09:32:35	1.125
--- stmt.c	2000/03/05 00:41:29
*************** expand_start_stmt_expr ()
*** 2025,2031 ****
    t = make_node (RTL_EXPR);
    resume_momentary (momentary);
    do_pending_stack_adjust ();
!   start_sequence_for_rtl_expr (t);
    NO_DEFER_POP;
    expr_stmts_for_value++;
    return t;
--- 2025,2031 ----
    t = make_node (RTL_EXPR);
    resume_momentary (momentary);
    do_pending_stack_adjust ();
!   start_sequence ();
    NO_DEFER_POP;
    expr_stmts_for_value++;
    return t;
Index: tree.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/tree.h,v
retrieving revision 1.132
diff -c -p -r1.132 tree.h
*** tree.h	2000/03/04 16:40:05	1.132
--- tree.h	2000/03/05 00:41:31
*************** extern void preserve_temp_slots		PARAMS 
*** 2452,2458 ****
  extern int aggregate_value_p		PARAMS ((tree));
  extern tree reorder_blocks		PARAMS ((tree,
  						struct rtx_def *));
- extern void free_temps_for_rtl_expr	PARAMS ((tree));
  extern void instantiate_virtual_regs	PARAMS ((tree, struct rtx_def *));
  extern void unshare_all_rtl		PARAMS ((tree, struct rtx_def *));
  extern int max_parm_reg_num		PARAMS ((void));
--- 2452,2457 ----
*************** extern struct rtx_def *store_expr		PARAM
*** 2486,2492 ****
  extern void check_max_integer_computation_mode	PARAMS ((tree));
  
  /* In emit-rtl.c */
- extern void start_sequence_for_rtl_expr		PARAMS ((tree));
  extern struct rtx_def *emit_line_note_after	PARAMS ((char *, int,
  							struct rtx_def *));
  extern struct rtx_def *emit_line_note		PARAMS ((char *, int));
--- 2485,2490 ----


More information about the Gcc-patches mailing list