[tree-ssa] Tail recursion improvement

[Zdenek Dvorak]

Hello,

>  >Index: tree-optimize.c
> As discussed, the tree-optimize.c change is wrong.  I did a new test cycle
> without the tree-optimize.c change.

I tried to get the tree-optimize.c change working; so I have moved both
pass_ch and pass_tail_recursion after pass_may_alias, and updated the
loop header copying to handle name tags.  After that I
encountered a few problems on the following testcase (taken from
libmudflap testsuite; note that the program is buggy and accesses
nonallocated memory):

int main ()
{
  int i = 10;
  char *x = (char *) malloc (i * sizeof (char));

  while (i--)
    {
      ++x;
      *x = 0;
    }

  return 0;
}

There seems to be a problem in tree-ssa.c:mark_def_sites; we process
operands of vdefs after the definitions, which prevents the phi node
for the type tag of x to be created.

After fixing this, I have run into a problem with dce; it removes the
*x assignment.  It does not do this without loop header copying, since
without it x has a name tag with DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL
set; but for the type tag it is not, and thus the statement is not
considered necessary.  I am not sure whether this is a bug at all
(if the program was not buggy, the writes to *x could indeed be safely
eliminated); but in any case it causes the libmudflap test to fail.
In case it indeed is a bug, where should it be fixed? Adding some more
conditions to mark_stmt_if_obviously_necessary? Or setting
DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL also for the type tag, somewhere?

Zdenek

Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.132
diff -c -3 -p -r1.1.4.132 tree-optimize.c
*** tree-optimize.c	2 Mar 2004 18:41:48 -0000	1.1.4.132
--- tree-optimize.c	4 Mar 2004 14:54:33 -0000
*************** init_tree_optimization_passes (void)
*** 287,294 ****
    NEXT_PASS (DUP_PASS (pass_dce));
    NEXT_PASS (pass_forwprop);
    NEXT_PASS (pass_phiopt);
-   NEXT_PASS (pass_ch);
    NEXT_PASS (pass_may_alias);
    NEXT_PASS (pass_del_pta);
    NEXT_PASS (pass_profile);
    NEXT_PASS (pass_lower_complex);
--- 287,295 ----
    NEXT_PASS (DUP_PASS (pass_dce));
    NEXT_PASS (pass_forwprop);
    NEXT_PASS (pass_phiopt);
    NEXT_PASS (pass_may_alias);
+   NEXT_PASS (pass_tail_recursion);
+   NEXT_PASS (pass_ch);
    NEXT_PASS (pass_del_pta);
    NEXT_PASS (pass_profile);
    NEXT_PASS (pass_lower_complex);
*************** init_tree_optimization_passes (void)
*** 300,306 ****
    NEXT_PASS (pass_dse);
    NEXT_PASS (DUP_PASS (pass_forwprop));
    NEXT_PASS (DUP_PASS (pass_phiopt));
-   NEXT_PASS (pass_tail_recursion);
    NEXT_PASS (pass_loop);
    NEXT_PASS (pass_ccp);
    NEXT_PASS (DUP_PASS (pass_redundant_phi));
--- 301,306 ----
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-ssa-loop.c
*** tree-ssa-loop.c	25 Feb 2004 03:22:47 -0000	1.1.2.10
--- tree-ssa-loop.c	4 Mar 2004 14:54:33 -0000
*************** mark_defs_for_rewrite (basic_block bb)
*** 152,157 ****
--- 152,164 ----
      {
        var = SSA_NAME_VAR (PHI_RESULT (stmt));
        bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ 
+       /* If we have a type_mem_tag, add it as well.  Due to rewriting the
+ 	 variable out of ssa, we lose its name tag, so we use type_mem_tag
+ 	 instead.  */
+       var = var_ann (var)->type_mem_tag;
+       if (var)
+ 	bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
      }
  
    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
*************** mark_defs_for_rewrite (basic_block bb)
*** 165,170 ****
--- 172,184 ----
  	{
  	  var = SSA_NAME_VAR (DEF_OP (defs, i));
  	  bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ 
+ 	  /* If we have a type_mem_tag, add it as well.  Due to rewriting the
+ 	     variable out of ssa, we lose its name tag, so we use type_mem_tag
+ 	     instead.  */
+ 	  var = var_ann (var)->type_mem_tag;
+ 	  if (var)
+ 	    bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
  	}
  
        vdefs = VDEF_OPS (ann);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.208
diff -c -3 -p -r1.1.4.208 tree-ssa.c
*** tree-ssa.c	3 Mar 2004 13:11:54 -0000	1.1.4.208
--- tree-ssa.c	4 Mar 2004 14:54:33 -0000
*************** mark_def_sites (struct dom_walk_data *wa
*** 622,630 ****
  	{
  	  VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
  
- 	  set_def_block (VDEF_RESULT (vdefs, i), bb);
  	  if (!TEST_BIT (kills, uid))
  	    set_livein_block (VDEF_OP (vdefs, i), bb);
  	}
      }
  
--- 622,630 ----
  	{
  	  VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
  
  	  if (!TEST_BIT (kills, uid))
  	    set_livein_block (VDEF_OP (vdefs, i), bb);
+ 	  set_def_block (VDEF_RESULT (vdefs, i), bb);
  	}
      }