Re: PATCH: New optimization: Partitioning hot/cold basic blocks

[Richard Henderson <rth at redhat dot com>]

On Fri, Feb 27, 2004 at 09:47:31AM -0800, Caroline Tice wrote:
> +     ret_val = (scan_ahead_for_unlikely_executed_note (BB_HEAD (e->src)) ==
> + 	       scan_ahead_for_unlikely_executed_note (BB_HEAD (e->dest)));

The number of times you're scanning instructions for this note
is bad.  You should just keep a bitmap or sbitmap, depending
on the expected density of the set bits.

>   {
> + 
...
> +  	
> +       }
> +   
> + }

Don't add silly whitespace.  Lots of ocurrences.

> !       if (round < last_round - 1
> + 	       && (round == last_round - 1)
> + 		  && (round <= last_round - 1)

I think these tests are confusing.  It would be much better to have
a predicate or nicely named boolean variable to accurately describe
what's being tested here.

Fold flag_reorder_blocks_and_partition into said predicates.

> + static
> + void color_basic_blocks (int *bb_colors, int *bb_has_label, 

Bad formatting.  Several ocurrences.

> + /* Find all the edges that cross between hot and cold sections.  */
...
> +  	  /* Check to see if cur_bb ends in an unconditional jump.  If
> +  	     so, there is nothing that needs to be done for it.  */

Well that would seem to deny the function block comment.
What exactly is this function supposed to be collecting?

> +  	  if ((GET_CODE (last_insn) == JUMP_INSN)
> +  	      && (! any_condjump_p (last_insn)))
> +  	    continue;

Redundant check form jump_insn.
Redundant parenthesis.  Lots of ocurrences.

> +  	  if ((GET_CODE (last_insn) != JUMP_INSN)
> +  	      && (succ1->dest != cur_bb->rbi->next))
> +  	    continue;

Another check for jump_insn?

I'm not sure what you're not just doing

	FOR_EACH_BB(bb)
	  for (e = bb->succ; e ; e = e->succ_next)

Of course, that means you're not necessarily capped at 2*n_basic_blocks,
which means crossing_edges needs to be allocated and reallocated within
this function.

Alternately, I might guess that you could use e->aux to mark those that
cross sections, so you don't have to allocate memory at all.  You'd have
to double-check that, since I don't know which aux bits are currently 
used by bb-reorder.  You might well be able to add your bits to those
datastructures, however.

A final alternative is to allocate a bit in e->flags.

> + /* If any destination of a crossing edge does not have a label, add label;
> +    Convert any fall-through crossing edges (for blocks that do not contain
> +    a jump) to unconditional jumps.   */
> + 
> + static 
> + void add_labels_and_missing_jumps (edge *crossing_edges, 
> +  				   int n_crossing_edges,
> +  				   int *bb_has_label, int *bb_has_jump)

The creating label part of this is wrong -- we have block_label that
will create or find labels for blocks on demand.  I see that there's
the no-jump fallthrough part remaining; perhaps this function becomes
clearer without the label bits.

> +   	  if (dest && (dest->index != -2)) /* Not EXIT BLOCK */

Never ever compare vs -2/-1 directly.

> +       if (fall_thru && (fall_thru->dest->index >= 0))

rtl_verify_flow_info assures us that we never fallthru to exit.

> +  	      /* Find the jump instruction.  */
> + 	      
> +  	      for (cur_insn = BB_HEAD (cur_bb); 
> + 		   cur_insn != NEXT_INSN (BB_END (cur_bb));
> +  		   cur_insn = NEXT_INSN (cur_insn))
> +  		if (GET_CODE (cur_insn) == JUMP_INSN)

The jump insn is always at the end.  Always.

> +  	      if (cond_jump)

Don't we already know that both edges already exist?

> +  		      /* Find label in fall_thru block. We've already added
> +  		         any missing labels, so there must be one. */

block_label.

> +  		  /* This is the case where both edges out of the basic
> +  		     block are crossing edges. Here we will fix up the
> + 		     fall through edge. The jump edge will be taken care
> + 		     of later.  */
> + 		  
> +  		  new_bb = force_nonfallthru (fall_thru);  

Seems like this new block should be reused for other crossings,
but I can't see how it would get found.

> + 		      REG_NOTES (BB_END (new_bb)) = gen_rtx_EXPR_LIST
> + 			                                  (REG_CROSSING_JUMP,
> + 							   NULL_RTX,
> + 							   NULL_RTX);

Don't all of these get added at the end?

> + static basic_block
> + find_jump_block  (rtx old_label, basic_block *block_list, int max_idx)

Again this seems like something that we shouldn't be searching for.
Either we can process all crossing edges incomming to each block and
create just the one bounce block (and never have to record it) or we
should have this placed in some lookaside data structure (like RBI).

> +   /* Find last, last hot, and last cold basic blocks.  These will be
> +      used as insertion points for new bb's containing unconditional
> +      jumps (to cross section boundaries).  */

Why wouldn't this be taken care of with the bb-reordering block
ordering data structures?

> +  	      /* Find the jump insn in cur_bb.  */
> + 	      
> +  	      found = 0;
> +  	      old_jump = NULL;
> +  	      for (cur_insn = BB_HEAD (cur_bb); 
> + 		   (cur_insn != NEXT_INSN (BB_END (cur_bb))) && !found; 
> + 		   cur_insn = NEXT_INSN (cur_insn))

Again, it's last.

> +  	      /* Check to make sure the jump instruction is a
> + 		 conditional jump.  */

We have predicates in jump.c for this sort of thing.

> +       /* Check to see if bb ends in an unconditional jump.  */
> + 
> +       if ((GET_CODE (last_insn) == JUMP_INSN)
> + 	  && (! any_condjump_p (last_insn)))
> + 	{
> + 	  succ = cur_bb->succ;
> + 
> + 	  if (succ->succ_next)
> + 	    {
> + 	      rtx set_src;
> + 	      if (GET_CODE (PATTERN (last_insn)) == SET)
> + 		set_src = SET_SRC (PATTERN (last_insn));
> + 	      else if (GET_CODE (PATTERN (last_insn)) == PARALLEL)
> + 		{
> + 		  set_src = XVECEXP (PATTERN (last_insn), 0, 0);
> + 		  if (GET_CODE (set_src) == SET)
> + 		    set_src = SET_SRC (set_src);
> + 		  else
> + 		    set_src = NULL_RTX;
> + 
> + 		  if (set_src && (GET_CODE (set_src) == REG))
> + 		    continue;
> + 		  else
> + 		    abort ();
> + 		}
> + 	      else
> + 		abort ();
> + 	    }
> + 

What kind of unconditional direct jump has two edges?  Are you
looking to exclude tablejump and computed jump here or what?
Again, there's predicates for this sort of thing in jump.c.

> *************** try_simplify_condjump (basic_block cbran
> *** 148,153 ****
> --- 149,163 ----
>       return false;
>     jump_dest_block = jump_block->succ->dest;
>   
> +   /* If we are partitioning hot/cold basic blocks, we don't want to
> +      mess up unconditional or indirect jumps that cross between hot
> +      and cold sections.  */
> +   
> +   if (flag_reorder_blocks_and_partition
> +       && (scan_ahead_for_unlikely_executed_note (BB_HEAD (jump_block)) !=
> + 	  scan_ahead_for_unlikely_executed_note (BB_HEAD (jump_dest_block))))
> +     return false;

Ok, you use this data outside your own pass.  This *definitely* 
wants some sort of basic_block/edge annotation.

> *************** try_crossjump_to_edge (int mode, edge e1
> *** 1367,1372 ****
> --- 1418,1430 ----
>     rtx newpos1, newpos2;
>     edge s;
>   
> +   /* If we have partitioned hot/cold basic blocks, it is a bad idea
> +      to try this optimization.  */
> + 
> +   if (flag_reorder_blocks_and_partition && no_new_pseudos)
> +     return false;

Hum?  I don't see why not.  You just want to avoid crossjumping
between hot/cold blocks.  I'm also quite certain that you don't
want to insert NOTE_INSN_UNLIKELY_EXECUTED_CODE or REG_CROSSING_JUMP
until late in the compilation process.  They'll just cause you 
problems trying to keep them up-to-date.

Also, you'll want to have verify_flow_info changes that validate
things like fallthru only between same sections.

> +   if (current_function_decl->decl.section_name)
> +     fprintf (asmfile, SECTION_FORMAT_STRING,
> + 	   TREE_STRING_POINTER (current_function_decl->decl.section_name));
> +   else
> +     fprintf (asmfile, SECTION_FORMAT_STRING, HOT_TEXT_SECTION_NAME);

Hmm?  Are you absolutely certain you don't want function_section()?

>   #ifndef HOT_TEXT_SECTION_NAME
> - #define HOT_TEXT_SECTION_NAME "text.hot"
> + #define HOT_TEXT_SECTION_NAME ".text"
>   #endif

This conflicts with existing usage of HOT_TEXT_SECTION_NAME.

>   #ifndef UNLIKELY_EXECUTED_TEXT_SECTION_NAME
> - #define UNLIKELY_EXECUTED_TEXT_SECTION_NAME "text.unlikely"
> + #define UNLIKELY_EXECUTED_TEXT_SECTION_NAME ".textunlikely"
>   #endif

Why?

> + static bool
> + is_jump_table_basic_block (rtx insn)

You mean something like tablejump_p?

> + 	  if (!in_unlikely_text_section())
> + 	    unlikely_text_section ();

Section changing should already take care of the if.

>   	case NOTE_INSN_BASIC_BLOCK:
> + 	  
> + 	  /* If we are performing the optimization that paritions
> + 	     basic blocks into hot & cold sections of the .o file,
> + 	     then at the start of each new basic block, before
> + 	     beginning to write code for the basic block, we need to
> + 	     check to see whether the basic block belongs in the hot
> + 	     or cold section of the .o file, and change the section we
> + 	     are writing to appropriately.  */
> + 	  
> + 	  if (flag_reorder_blocks_and_partition)
> + 	    if (in_unlikely_text_section())
> + 	      if (!(scan_ahead_for_unlikely_executed_note (insn)))
> + 		text_section ();

NOTE_INSN_BASIC_BLOCK occurs after the CODE_LABEL.

> !       if (!unlikely_section_label_printed)
> ! 	{
> ! 	  fprintf (asm_out_file, "_%s_unlikely_section:\n", 
> ! 		   current_function_name ());
> ! 	  unlikely_section_label_printed = true;
> ! 	}

This should be some debug callback, since dwarf2 is going to want
to handle this in some other way.  And it would have to be two
leading underscores to get it out of the user's namespace.

> + #define SECTION_FORMAT_STRING ".section\t\"%s\"\n\t.align 2\n"

What is this for?



r~