split_edge, reg-stack and function.c fix

[Jan Hubicka <hubicka@atrey.karlin.mff.cuni.cz>]

Hi
While looking at the asm outputs, I've found following code:
	jne .L11
        jmp .L9
.L15:
	fxch %st(2)
        .p2align 4,,7
.L9:
        <loop body>
        cmpb $1,%ah
        je .L15
.L16:
.L17:

Despite the fact, that the code is ugly (the entering condition can be
predicted to be true)
(BTW also note the redundant label L17. Why this happends? There are
few notes between in the .stack dump, but jump IMO ought to remove it or
not?),
The problem I am shooting for is that the alignment pseudo is *inside* the
loop, resulting code is much slower, because it has to eat all those nops
every iteration.

I it is caused by reg-stack by by coexistence of two problems:
1) The LOOP_BEG function is placed incorrectly before the basic block for
   the jmp L9 instruction.
2) Shorten branches is done before reg-stack so alginment of most branches
   touched by reg-stack is completely wrong.


The second problem is trivial to fix. To fix first problem in the old
reg-stack code is quite a lot of work (because it's edge splitting code
is messy).

So I've fixed it only for my new rewrite (altrought this change is usefull
for compiler with old reg-stack as well),
I've just updated split_edge to handle this nicely. It now looks whether
it is puting block before first block of loop and moves loop_beg notes
when needed.

I've done this using few new functions, just to avoid split_edge
from another bloat to keep it readable and also because I think some
other block manipulation in flow.c might like this code as well.

This also showed problem with the function.c messing up the flow info
and then calling commit edge insertions. I've fixed this by commenting
out the wrong update, ensuring that we are outputing after all important
notes (so once flow2 info is done, we get correct results) and for sure by
calling commit_edge_insertions before epilogue
is generated (so only prologue is done) so in time flow info is OK.

Interesting side effect is that alignments are now correct in functions
immediately starting by the loop. Orriginaly there was missing alignment,
because LOOP_BEG was kept before the prologue.

I've also attached patch to i386.c in new_ia32_branch to make length
function happy about this code.

Honza

Sun Jul  4 06:01:01 CEST 1999  Jan Hubicka  <hubicka@freesoft.cz>
	* flow.c (loops_starting_here): New function.
	(loops_ending_here): New function.
	(end_of_loop): New function.
	(move_loop_beg_notes): New function.
	(split_edge): 
	* toplev.c (rest_of_compilation): Do shorted_branches after regstack.
	* function.c (thread_prologue_and_epilogue_insns): Mess up flow info
	in more split_edge friendly way, call commit_edge_insertions before
	this mess is done.
	* i386.c (ix86_attr_length_default): Handle FXCH nicely.

*** flow.c.orig	Fri Jul  2 05:08:19 1999
--- flow.c	Sun Jul  4 05:31:01 1999
*************** mark_critical_edges ()
*** 1158,1163 ****
--- 1159,1247 ----
      }
  }
  
+ /* Return number of loops starting in this basic block.  */
+ static int
+ loops_starting_here (block)
+      basic_block block;
+ {
+   rtx insn;
+   int n = 0;
+   insn = PREV_INSN (block->head);
+   /* Go trought the note insns and scan for NOTE_INSN_LOOP_BEG  */
+   while (insn && GET_CODE (insn) == NOTE
+ 	 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
+     {
+       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ 	n++;
+       insn = PREV_INSN (insn);
+     }
+   return n;
+ }
+ 
+ /* Return number of loops ending in this basic block.  */
+ static int
+ loops_ending_here (block)
+      basic_block block;
+ {
+   rtx insn;
+   int n = 0;
+   insn = NEXT_INSN (block->end);
+   /* Go trought the note insns and scan for NOTE_INSN_LOOP_BEG  */
+   while (insn && GET_CODE (insn) == NOTE
+ 	 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
+     {
+       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
+ 	n++;
+       insn = NEXT_INSN (insn);
+     }
+   return n;
+ }
+ 
+ /* Find end of loop starting in this basic block ends.  */
+ static basic_block
+ end_of_loop (block)
+      basic_block block;
+ {
+   int nested = 0;
+   int n = block->index;
+   basic_block curr;
+   do
+     {
+       curr = BASIC_BLOCK (n);
+       nested += loops_starting_here (curr);
+       nested -= loops_ending_here (curr);
+       n++;
+       if (n >= n_basic_blocks && nested > 0)
+ 	abort ();
+     }
+   while (nested > 0);
+   return curr;
+ }
+ 
+ /*  Move all LOOP_BEG notes before INSN before INSN2.  */
+ static void
+ move_loop_beg_notes (insn, insn2)
+      rtx insn, insn2;
+ {
+   rtx prev;
+   insn = PREV_INSN (insn);
+   /* Go trought the note insns and scan for NOTE_INSN_LOOP_BEG  */
+   while (insn && GET_CODE (insn) == NOTE
+ 	 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
+     {
+       prev = PREV_INSN (insn);
+ 
+       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+       {
+         /* This ought to be safe, because no head or end pointer can point to
+            loop notes.  */
+ 	delete_insn (insn);
+ 	emit_note_before (NOTE_INSN_LOOP_BEG, insn2);
+       }
+       insn = prev;
+     }
+ }
+ 
  /* Split a (typically critical) edge.  Return the new block.
     Abort on abnormal edges. 
  
*************** split_edge (edge_in)
*** 1349,1354 ****
--- 1433,1451 ----
        emit_label_before (new_label, bb_note);
        bb->head = new_label;
      }
+   /* If we appeared after LOOP_BEG note, ensure, that we are really inside
+      loop.  This is done by checking whether we are reached from inside of
+      the loop.  */
+   if (loops_starting_here (bb))
+     {
+       basic_block end = end_of_loop (bb);
+       if (edge_in->src->index < bb->index 
+ 	  || edge_in->src->index > end->index)
+ 	{
+ 	  /* We are outside loop, move the notes correspondingly.  */
+ 	  move_loop_beg_notes (bb->head, old_succ->head);
+ 	}
+     }
  
    return bb;
  }
*** toplev.c~	Mon Jun 21 22:52:56 1999
--- toplev.c	Sun Jul  4 05:36:38 1999
*************** rest_of_compilation (decl)
*** 4377,4388 ****
      }
  #endif
  
-   /* Shorten branches.  */
-   TIMEVAR (shorten_branch_time,
- 	   {
- 	     shorten_branches (get_insns ());
- 	   });
- 
  #ifdef STACK_REGS
    if (stack_reg_dump)
      open_dump_file (".stack", decl_printable_name (decl, 2));
--- 4377,4382 ----
*************** rest_of_compilation (decl)
*** 4397,4402 ****
--- 4391,4403 ----
      }
  #endif
  
+   /* Shorten branches.  */
+   TIMEVAR (shorten_branch_time,
+ 	   {
+ 	     shorten_branches (get_insns ());
+ 	   });
+ 
+ 
    /* Now turn the rtl into assembler code.  */
  
    TIMEVAR (final_time,
*** config/i386/i386.c.fp	Fri Jul  2 08:18:53 1999
--- config/i386/i386.c	Sun Jul  4 05:38:38 1999
*************** ix86_attr_length_default (insn)
*** 4996,5003 ****
--- 4996,5005 ----
      case TYPE_FOP1:
      case TYPE_FMUL:
      case TYPE_FDIV:
      case TYPE_FPSPC:
      case TYPE_FCMOV:
+     case TYPE_FXCH:
      case TYPE_IBR:
        break;
  
*** function.c.old	Sun Jul  4 06:26:41 1999
--- function.c	Sun Jul  4 06:41:15 1999
*************** void
*** 6683,6690 ****
  thread_prologue_and_epilogue_insns (f)
       rtx f ATTRIBUTE_UNUSED;
  {
-   int insertted = 0;
- 
    prologue = 0;
  #ifdef HAVE_prologue
    if (HAVE_prologue)
--- 6683,6688 ----
*************** thread_prologue_and_epilogue_insns (f)
*** 6713,6719 ****
  	    abort ();
  
  	  insert_insn_on_edge (seq, ENTRY_BLOCK_PTR->succ);
! 	  insertted = 1;
  	}
        else
  	emit_insn_after (seq, f);
--- 6711,6717 ----
  	    abort ();
  
  	  insert_insn_on_edge (seq, ENTRY_BLOCK_PTR->succ);
! 	  commit_edge_insertions ();
  	}
        else
  	emit_insn_after (seq, f);
*************** thread_prologue_and_epilogue_insns (f)
*** 6761,6766 ****
--- 6759,6767 ----
  	  bb = e->src;
  	  tail = bb->end;
  
+ 	  while (NEXT_INSN (tail) && GET_CODE (NEXT_INSN (tail)) == NOTE)
+ 	    tail = NEXT_INSN (tail);
+ 
  	  /* ??? If the last insn of the basic block is a jump, then we
  	     are creating a new basic block.  Wimp out and leave these
  	     insns outside any block.  */
*************** thread_prologue_and_epilogue_insns (f)
*** 6834,6842 ****
--- 6835,6850 ----
  	      emit_insns_before (first_use, tail);
  	    emit_note_after (NOTE_INSN_EPILOGUE_BEG, prev);
  
+ #if 0
  	    /* Update the tail of the basic block.  */
+ 	    /* ??? Thinks are not so easy, because in block ended by jump,
+ 	       the jump insn gets inside of basic block. It is better to keep
+ 	       flow info broken in a way, that instructions are outside block.
+ 	       This will be easily fixed by removing all this stuff and using
+ 	       emit_insn_on_edge instead.  */
  	    if (bb)
  	      bb->end = tail;
+ #endif
  
  	    /* Retain a map of the epilogue insns.  */
  	    epilogue = record_insns (GET_CODE (seq) == SEQUENCE ? seq : tail);
*************** thread_prologue_and_epilogue_insns (f)
*** 6845,6852 ****
      }
  #endif
  
-   if (insertted)
-     commit_edge_insertions ();
  }
  
  /* Reposition the prologue-end and epilogue-begin notes after instruction
--- 6853,6858 ----