RFA: Use fixup_fallthru_exit_predecessor only for !HAVE_prologue targets, and only after reload (Was: Re: RFA: remove fixup_fallthru_exit_predecessor)

[Joern Rennecke <joern dot rennecke at superh dot com>]

> Oops, I just see that we still have targets that output assembler epilogues.
> I suppose the right thing to do is to make thread_prologue_and_epilogue_insns
> always check for a fall-through edge to the exit block if we couldn't
> use a return, and if we can't use an rtl prologue either, to generate
> a new basic block at the end of the function and redirect all the exit edges
> to it.
> 
> This does not give optimal code, but at lest it should work.
> There might be some targets that have both high pressure on the return
> register and asm epilogues, so trying to use fixup_fallthru_exit_predecessor
> just for some targets would be fraught with danger.
> If optimal code is desired, it is better to use rtl epilogues anyway.  And
> besides, AFAIK most functions still end up with the exit block at the end.
> 
> Right now I am searching for a testcase.  I've put an abort where the fix-up
> code would go and try to build an sparc-elf cross.

I've found a testcase already in building unwind-dw2.o for sparc-elf.

Basic block reordering happens after epilogue generation, and it can
also result in a fall-through to the exit block from mid-function.
So for the asm epilogue targets, I brought back
fixup_fallthru_exit_predecessor.  It is now called only after reload, and
only if HAVE_epilogue is false too.
Doing the epilogue fixup by hand also proved extremely cumbersome, so I
basically do a basic block reordering pass without the reordering in
thread_prologue_and_epilogue_insns.
I've also found that fixup_fallthrough_predecessor has to handle the special
case of the first block having a fall-through exit edge.
The rest is the same as in the previous patch.

I have bootstrapped/regtested this on i686-pc-linux-gnu, and build for
sparc-elf; however, I could only do compile tests for the latter, because
the linker script didn't work (it made some read-only section overlapping
with bss).
I am now bootstrappping on sparc-sun-solaris2.8; it is currently building
stage3.

2004-06-09  J"orn Rennecke <joern.rennecke@superh.com>

	* basic-block.h (could_fall_through): Declare.
	* cfganal.c (can_fallthru): Succeed if the target is EXIT_BLOCK_PTR.
	Fail if the source already has a fallthrough edge to the exit
	block pointer.
	(could_fall_through): New function.
	* cfgbuild.c (make_edges): Check if we already have a fallthrough
	edge to the exit block pointer.
	* cfglayout.c (fixup_fallthru_exit_predecessor): Check that it is
	not called before reload has completed.
	Handle special case of first block having a fall-through exit edge.
	(cfg_layout_finalize): Don't call it before reload or if we have
	rtl epilogues.
	(fixup_reorder_chain): A fall through to the exit block does not
	require the block to come last.  Add sanity checks.
	* cfgrtl.c (rtl_split_edge): Add special handling of fall through
	edges to the exit block.
	* function.c (cfglayout.h): #include.
	(thread_prologue_and_epilogue_insns): If we have neither return nor
	epilogue, but a fall through to the exit block from mid-function,
	force a non-fall-through exit.
	* Makefile.in (function.o): Depend on CFGLAYOUT_H.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1293
diff -p -r1.1293 Makefile.in
*** Makefile.in	5 Jun 2004 20:58:06 -0000	1.1293
--- Makefile.in	9 Jun 2004 18:45:34 -0000
*************** varasm.o : varasm.c $(CONFIG_H) $(SYSTEM
*** 1757,1763 ****
     flags.h function.h $(EXPR_H) hard-reg-set.h $(REGS_H) \
     output.h c-pragma.h toplev.h xcoffout.h debug.h $(GGC_H) $(TM_P_H) \
     $(HASHTAB_H) $(TARGET_H) langhooks.h gt-varasm.h real.h
! function.o : function.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
     flags.h function.h $(EXPR_H) $(OPTABS_H) libfuncs.h $(REGS_H) hard-reg-set.h \
     insn-config.h $(RECOG_H) output.h toplev.h except.h $(HASHTAB_H) $(GGC_H) \
     $(TM_P_H) langhooks.h gt-function.h $(TARGET_H) basic-block.h
--- 1757,1764 ----
     flags.h function.h $(EXPR_H) hard-reg-set.h $(REGS_H) \
     output.h c-pragma.h toplev.h xcoffout.h debug.h $(GGC_H) $(TM_P_H) \
     $(HASHTAB_H) $(TARGET_H) langhooks.h gt-varasm.h real.h
! function.o : function.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
!    $(TREE_H) $(CFGLAYOUT_H) \
     flags.h function.h $(EXPR_H) $(OPTABS_H) libfuncs.h $(REGS_H) hard-reg-set.h \
     insn-config.h $(RECOG_H) output.h toplev.h except.h $(HASHTAB_H) $(GGC_H) \
     $(TM_P_H) langhooks.h gt-function.h $(TARGET_H) basic-block.h
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.197
diff -p -r1.197 basic-block.h
*** basic-block.h	3 Jun 2004 12:07:36 -0000	1.197
--- basic-block.h	9 Jun 2004 18:45:34 -0000
*************** extern void find_sub_basic_blocks (basic
*** 626,631 ****
--- 626,632 ----
  extern void find_many_sub_basic_blocks (sbitmap);
  extern void rtl_make_eh_edge (sbitmap *, basic_block, rtx);
  extern bool can_fallthru (basic_block, basic_block);
+ extern bool could_fall_through (basic_block, basic_block);
  extern void flow_nodes_print (const char *, const sbitmap, FILE *);
  extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
  extern void alloc_aux_for_block (basic_block, int);
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.42
diff -p -r1.42 cfganal.c
*** cfganal.c	13 May 2004 06:39:32 -0000	1.42
--- cfganal.c	9 Jun 2004 18:45:35 -0000
*************** bool
*** 103,119 ****
  can_fallthru (basic_block src, basic_block target)
  {
    rtx insn = BB_END (src);
!   rtx insn2 = target == EXIT_BLOCK_PTR ? NULL : BB_HEAD (target);
  
    if (src->next_bb != target)
      return 0;
  
    if (insn2 && !active_insn_p (insn2))
      insn2 = next_active_insn (insn2);
  
    /* ??? Later we may add code to move jump tables offline.  */
    return next_active_insn (insn) == insn2;
  }
  
  /* Mark the back edges in DFS traversal.
     Return nonzero if a loop (natural or otherwise) is present.
--- 103,144 ----
  can_fallthru (basic_block src, basic_block target)
  {
    rtx insn = BB_END (src);
!   rtx insn2;
!   edge e;
  
+   if (target == EXIT_BLOCK_PTR)
+     return true;
    if (src->next_bb != target)
      return 0;
+   for (e = src->succ; e; e = e->succ_next)
+     if (e->dest == EXIT_BLOCK_PTR
+ 	&& e->flags & EDGE_FALLTHRU)
+     return 0;
  
+   insn2 = BB_HEAD (target);
    if (insn2 && !active_insn_p (insn2))
      insn2 = next_active_insn (insn2);
  
    /* ??? Later we may add code to move jump tables offline.  */
    return next_active_insn (insn) == insn2;
  }
+ 
+ /* Return nonzero if we could reach target from src by falling through,
+    if the target was made adjacent.  If we already have a fall-through
+    edge to the exit block, we can't do that.  */
+ bool
+ could_fall_through (basic_block src, basic_block target)
+ {
+   edge e;
+ 
+   if (target == EXIT_BLOCK_PTR)
+     return true;
+   for (e = src->succ; e; e = e->succ_next)
+     if (e->dest == EXIT_BLOCK_PTR
+ 	&& e->flags & EDGE_FALLTHRU)
+     return 0;
+   return true;
+ }
  
  /* Mark the back edges in DFS traversal.
     Return nonzero if a loop (natural or otherwise) is present.
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.47
diff -p -r1.47 cfgbuild.c
*** cfgbuild.c	3 Jun 2004 12:07:38 -0000	1.47
--- cfgbuild.c	9 Jun 2004 18:45:35 -0000
*************** make_edges (rtx label_value_list, basic_
*** 267,272 ****
--- 267,273 ----
        rtx insn, x;
        enum rtx_code code;
        int force_fallthru = 0;
+       edge e;
  
        if (GET_CODE (BB_HEAD (bb)) == CODE_LABEL
  	  && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
*************** make_edges (rtx label_value_list, basic_
*** 389,394 ****
--- 390,401 ----
  
        /* Find out if we can drop through to the next block.  */
        insn = NEXT_INSN (insn);
+       for (e = bb->succ; e; e = e->succ_next)
+ 	if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU)
+ 	  {
+ 	    insn = 0;
+ 	    break;
+ 	  }
        while (insn
  	     && GET_CODE (insn) == NOTE
  	     && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
Index: cfglayout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.59
diff -p -r1.59 cfglayout.c
*** cfglayout.c	25 May 2004 12:54:53 -0000	1.59
--- cfglayout.c	9 Jun 2004 18:45:35 -0000
*************** fixup_reorder_chain (void)
*** 714,719 ****
--- 714,723 ----
  		      && invert_jump (bb_end_insn,
  				      label_for_bb (e_fall->dest), 0))
  		    {
+ #ifdef ENABLE_CHECKING
+ 		      if (!could_fall_through (e_taken->src, e_taken->dest))
+ 			abort ();
+ #endif
  		      e_fall->flags &= ~EDGE_FALLTHRU;
  		      e_taken->flags |= EDGE_FALLTHRU;
  		      update_br_prob_note (bb);
*************** fixup_reorder_chain (void)
*** 731,736 ****
--- 735,744 ----
  	      else if (invert_jump (bb_end_insn,
  				    label_for_bb (e_fall->dest), 0))
  		{
+ #ifdef ENABLE_CHECKING
+ 		  if (!could_fall_through (e_taken->src, e_taken->dest))
+ 		    abort ();
+ #endif
  		  e_fall->flags &= ~EDGE_FALLTHRU;
  		  e_taken->flags |= EDGE_FALLTHRU;
  		  update_br_prob_note (bb);
*************** fixup_reorder_chain (void)
*** 770,776 ****
  	    continue;
  
  	  /* A fallthru to exit block.  */
! 	  if (!bb->rbi->next && e_fall->dest == EXIT_BLOCK_PTR)
  	    continue;
  	}
  
--- 778,784 ----
  	    continue;
  
  	  /* A fallthru to exit block.  */
! 	  if (e_fall->dest == EXIT_BLOCK_PTR)
  	    continue;
  	}
  
*************** verify_insn_chain (void)
*** 910,923 ****
      abort ();
  }
  
! /* The block falling through to exit must be the last one in the
!    reordered chain.  Ensure that this condition is met.  */
  static void
  fixup_fallthru_exit_predecessor (void)
  {
    edge e;
    basic_block bb = NULL;
  
    for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
      if (e->flags & EDGE_FALLTHRU)
        bb = e->src;
--- 918,937 ----
      abort ();
  }
  
! /* If we have assembler epilogues, the block falling through to exit must
!    be the last one in the reordered chain when we reach final.  Ensure
!    that this condition is met.  */
  static void
  fixup_fallthru_exit_predecessor (void)
  {
    edge e;
    basic_block bb = NULL;
  
+   /* This transformation is not valid before reload, because we might separate
+      a call from the instruction that copies the return value.  */
+   if (! reload_completed)
+     abort ();
+ 
    for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
      if (e->flags & EDGE_FALLTHRU)
        bb = e->src;
*************** fixup_fallthru_exit_predecessor (void)
*** 926,931 ****
--- 940,957 ----
      {
        basic_block c = ENTRY_BLOCK_PTR->next_bb;
  
+       /* If the very first block is the one with the fall-through exit
+ 	 edge, we have to split that block.  */
+       if (c == bb)
+ 	{
+ 	  bb = split_block (bb, NULL)->dest;
+ 	  initialize_bb_rbi (bb);
+ 	  bb->rbi->next = c->rbi->next;
+ 	  c->rbi->next = bb;
+ 	  bb->rbi->footer = c->rbi->footer;
+ 	  c->rbi->footer = NULL;
+ 	}
+ 
        while (c->rbi->next != bb)
  	c = c->rbi->next;
  
*************** cfg_layout_finalize (void)
*** 1176,1182 ****
    verify_flow_info ();
  #endif
    rtl_register_cfg_hooks ();
!   fixup_fallthru_exit_predecessor ();
    fixup_reorder_chain ();
  
  #ifdef ENABLE_CHECKING
--- 1202,1213 ----
    verify_flow_info ();
  #endif
    rtl_register_cfg_hooks ();
!   if (reload_completed
! #ifdef HAVE_epilogue
!       && !HAVE_epilogue
! #endif
!       )
!     fixup_fallthru_exit_predecessor ();
    fixup_reorder_chain ();
  
  #ifdef ENABLE_CHECKING
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.120
diff -p -r1.120 cfgrtl.c
*** cfgrtl.c	4 Jun 2004 15:01:49 -0000	1.120
--- cfgrtl.c	9 Jun 2004 18:45:35 -0000
*************** rtl_split_edge (edge edge_in)
*** 1336,1342 ****
    else
      before = NULL_RTX;
  
!   bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
  
    /* ??? This info is likely going to be out of date very soon.  */
    if (edge_in->dest->global_live_at_start)
--- 1336,1354 ----
    else
      before = NULL_RTX;
  
!   /* If this is a fall through edge to the exit block, the blocks might be
!      not adjacent, and the right place is the after the source.  */
!   if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR)
!     {
!       before = NEXT_INSN (BB_END (edge_in->src));
!       if (before
! 	  && GET_CODE (before) == NOTE
! 	  && NOTE_LINE_NUMBER (before) == NOTE_INSN_LOOP_END)
! 	before = NEXT_INSN (before);
!       bb = create_basic_block (before, NULL, edge_in->src);
!     }
!   else
!     bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
  
    /* ??? This info is likely going to be out of date very soon.  */
    if (edge_in->dest->global_live_at_start)
Index: function.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/function.c,v
retrieving revision 1.520
diff -p -r1.520 function.c
*** function.c	3 Jun 2004 12:07:40 -0000	1.520
--- function.c	9 Jun 2004 18:45:38 -0000
*************** Software Foundation, 59 Temple Place - S
*** 63,68 ****
--- 63,69 ----
  #include "integrate.h"
  #include "langhooks.h"
  #include "target.h"
+ #include "cfglayout.h"
  
  #ifndef LOCAL_ALIGNMENT
  #define LOCAL_ALIGNMENT(TYPE, ALIGNMENT) ALIGNMENT
*************** thread_prologue_and_epilogue_insns (rtx 
*** 7564,7583 ****
  	}
      }
  #endif
  #ifdef HAVE_epilogue
    if (HAVE_epilogue)
      {
-       /* Find the edge that falls through to EXIT.  Other edges may exist
- 	 due to RETURN instructions, but those don't need epilogues.
- 	 There really shouldn't be a mixture -- either all should have
- 	 been converted or none, however...  */
- 
-       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- 	if (e->flags & EDGE_FALLTHRU)
- 	  break;
-       if (e == NULL)
- 	goto epilogue_done;
- 
        start_sequence ();
        epilogue_end = emit_note (NOTE_INSN_EPILOGUE_BEG);
  
--- 7565,7584 ----
  	}
      }
  #endif
+   /* Find the edge that falls through to EXIT.  Other edges may exist
+      due to RETURN instructions, but those don't need epilogues.
+      There really shouldn't be a mixture -- either all should have
+      been converted or none, however...  */
+ 
+   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+     if (e->flags & EDGE_FALLTHRU)
+       break;
+   if (e == NULL)
+     goto epilogue_done;
+ 
  #ifdef HAVE_epilogue
    if (HAVE_epilogue)
      {
        start_sequence ();
        epilogue_end = emit_note (NOTE_INSN_EPILOGUE_BEG);
  
*************** thread_prologue_and_epilogue_insns (rtx 
*** 7603,7609 ****
--- 7604,7629 ----
        insert_insn_on_edge (seq, e);
        inserted = 1;
      }
+   else
  #endif
+     {
+       basic_block cur_bb;
+ 
+       if (! next_active_insn (BB_END (e->src)))
+ 	goto epilogue_done;
+       /* We have a fall-through edge to the exit block, the source is not
+          at the end of the function, and there will be an assembler epilogue
+          at the end of the function.
+          We can't use force_nonfallthru here, because that would try to
+          use return.  Inserting a jump 'by hand' is extremely messy, so
+ 	 we take advantage of cfg_layout_finalize using
+ 	fixup_fallthru_exit_predecessor.  */
+       cfg_layout_initialize ();
+       FOR_EACH_BB (cur_bb)
+ 	if (cur_bb->index >= 0 && cur_bb->next_bb->index >= 0)
+ 	  cur_bb->rbi->next = cur_bb->next_bb;
+       cfg_layout_finalize ();
+     }
  epilogue_done:
  
    if (inserted)