bb-reorder rewrite

[Jason Eckhardt]

On Mon, 22 May 2000, Richard Henderson wrote:

> 
> What happened is that jump2 decided to fix up several of the jumps
> by *undoing* the rearrangement bb-reorder had effected.
> 
> Given that this sort of thing is possible, and that long-term we'd
> like to reduce or eliminate jump_optimize, it seems clear that
> bb-reorder should do the entire transformation itself.

  Right. I had also thought about this since I wanted to try reordering
  blocks earlier. But cleanup_cfg will also undo things. Now that should
  be solved with this work.

>
>  
>     "Profile Guided Code Positioning"
>     Pettis and Hanson; PLDI '90.
>+ 
>+    TODO:
>+ 
>+ 
>+    (3) Invent a method by which sufficiently non-predicted code can
>+        be moved to either the end of the section or another section
>+        entirely.  Some sort of NOTE_INSN note would work fine.
>+ 

  This is also mentioned in the above paper. They actually collect
  all the not-predicted code hunks (from every function) together into their
  own section.
  Then all the functions (with the frequently executed code left) are able
  to be crammed together, fitting more of them to each memory page.


>!       /* ??? Get rid of this loop, and track which blocks are not yet
>! 	 placed more directly, so as to avoid the O(N^2) worst case.
>! 	 Perhaps keep a doubly-linked list of all to-be-placed blocks;
>! 	 remove from the list as we place.  The head of that list is
>! 	 what we're looking for here.  */
>  
>!       for (i = 0; i <= nbb_m1; ++i)
>  	{
>! 	  basic_block bb = BASIC_BLOCK (i);
>! 	  if (! RBI (bb)->visited)
>  	    {
>! 	      next = bb;
>! 	      break;
>  	    }
>  	}




  Could we just make this whole body "while (next)" instead of coding
  the loop with "goto restart"?

>!  restart:
>!       RBI (prev)->next = bb;
>!       new_index = RBI (prev)->index + 1;
>!       RBI (bb)->index = new_index;
  [...]
>  
>!   /* In the absense of prediction, disturb things as little as possible

                    of a prediction

>!      by selecting the old "next" block from the list of successors.  If
>!      there had been a fallthru edge, that will be the one.  */
  [...]

>  
>!   /* Make sure we didn't select a silly next block.  */
>!   if (!next || next == EXIT_BLOCK_PTR || RBI (next)->visited)

        ! next

  [...]

>!       }
>!   if (next)
>!     {
>!       bb = next;
>!       goto restart;
>!     }
>  
>!   return prev;
>  }
>  

  This section looks suspect:

>!       /* Disconnect the existing edge from the target block.  */
>!       {
>! 	edge *pe = &e_fall->dest->pred; 
>!         for (e = *pe; e != e_fall; pe = &e->pred_next, e = *pe)
>! 	  continue;
>! 	*pe = e->pred_next;
>!       }
>! 
>!       /* Link to new block.  */
>!       make_edge (NULL, nb, e_fall->dest, 0);
>!       nb->pred = e_fall;
>!       e_fall->dest = nb;


  It appears that e_fall gets disconnected properly, but its pred_next
  field is never updated. Perhaps it should be zeroed?

  Perhaps this code should be factored out into something like
  a "redirect_edge" or "delete_edge" function. I can see this being useful
  elsewhere in the future.
  
  jason