This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: [patches] Updated alignment optimization patch


> Hi,
> but I am optimistic now. 

... and I was overoptimistics.  After fixing rest of SH target I got into
rare failure, where the alignment was incorrect.  Problem is that at
boundary between data and code, the alignment is needed to fit the minimal
instruction length requirement.  This is not accompilished by LABEL_ALIGNMENT,
as I would expect, but by LABEL_ALIGN_AFTER_BARRIER.  This is because in
other cases, the label alignments is not good idea, when we are in the data.

So I made the patch more safe in this area.  I am keeping old semantic
of LABEL_ALIGN_AFTER_BARRIER now done after each barrier, and instead
make new JUMP_ALIGN to control alignment of common branches.
This is consistent with the idea of INDIRECT_JUMP_ALIGN etc.

I am defaulting LABEL_ALIGN_AFTER_BARRIER to 1 and JUMP_ALIGN to align_jumps,
as this is probably what user wants.  The align_jumps defaults to 1
with Os on all platforms, so this should be finally safe. Hope so.

Re-started testing on i686 and ARM, SH testing in late testsuite passes.
OK if it passes?

Honza

Thu Jul 26 16:15:27 CEST 2001  Jan Hubicka  <jh@suse.cz>

	* final.c (compute_alignments): New function.
	(init_insn_lengths): Do not care label_align.
	(LABEL_ALIGN_AFTER_BARRIER): Default to 1.
	(LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP): Default to 0.
	(JUMP_ALIGN, JUMP_ALIGN_MAX_SKIP): New.
	(shorted_branches): Realloc label_align array; do
	not call init_insn_lengths; Do not care about loop alignments.
	* output.h (compute_alignments): Declare.
	* toplev.c (rest_of_compilation): Call compute_alignments.

Index: final.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/final.c,v
retrieving revision 1.189
diff -c -3 -p -r1.189 final.c
*** final.c	2001/07/29 02:10:41	1.189
--- final.c	2001/07/29 18:17:13
*************** static struct label_alignment *label_ali
*** 632,642 ****
  void
  init_insn_lengths ()
  {
-   if (label_align)
-     {
-       free (label_align);
-       label_align = 0;
-     }
    if (uid_shuid)
      {
        free (uid_shuid);
--- 632,637 ----
*************** get_attr_length (insn)
*** 780,790 ****
  #endif
  
  #ifndef LABEL_ALIGN_AFTER_BARRIER
! #define LABEL_ALIGN_AFTER_BARRIER(LABEL) align_jumps_log
  #endif
  
  #ifndef LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP
! #define LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP (align_jumps-1)
  #endif
  
  #ifndef ADDR_VEC_ALIGN
--- 775,793 ----
  #endif
  
  #ifndef LABEL_ALIGN_AFTER_BARRIER
! #define LABEL_ALIGN_AFTER_BARRIER(LABEL) 1
  #endif
  
  #ifndef LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP
! #define LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP 0
! #endif
! 
! #ifndef JUMP_ALIGN
! #define JUMP_ALIGN(LABEL) align_jumps_log
! #endif
! 
! #ifndef JUMP_ALIGN_MAX_SKIP
! #define JUMP_ALIGN_MAX_SKIP (align_jumps-1)
  #endif
  
  #ifndef ADDR_VEC_ALIGN
*************** insn_current_reference_address (branch)
*** 935,940 ****
--- 938,1026 ----
  }
  #endif /* HAVE_ATTR_length */
  
+ void
+ compute_alignments ()
+ {
+   int i;
+   int log, max_skip, max_log;
+ 
+ 
+   /* We must do some computations even when not actually shortening, in
+      order to get the alignment information for the labels.  */
+ 
+   if (label_align)
+     {
+       free (label_align);
+       label_align = 0;
+     }
+ 
+   max_labelno = max_label_num ();
+   min_labelno = get_first_label_num ();
+   label_align = (struct label_alignment *) xcalloc ((max_labelno - min_labelno + 1),
+ 	     sizeof (struct label_alignment));
+ 
+   /* If not optimizing or optimizing for size, don't assign any alignments.  */
+   for (i = 0; i < n_basic_blocks; i++)
+     {
+       basic_block bb = BASIC_BLOCK (i);
+       rtx label = bb->head;
+       int fallthru_frequency = 0, branch_frequency = 0, has_fallthru = 0;
+       edge e;
+ 
+       if (GET_CODE (label) != CODE_LABEL)
+ 	continue;
+       max_log = LABEL_ALIGN (label);
+       max_skip = LABEL_ALIGN_MAX_SKIP;
+ 
+       for (e = bb->pred; e; e = e->pred_next)
+ 	{
+ 	  if (e->flags & EDGE_FALLTHRU)
+ 	    has_fallthru = 1, fallthru_frequency += EDGE_FREQUENCY (e);
+ 	  else
+ 	    branch_frequency += EDGE_FREQUENCY (e);
+ 	}
+ 
+       /* There are two purposes to align block with no fallthru incomming edge:
+ 	 1) to avoid fetch stalls when branch destination is near cache boundary
+ 	 2) to improve cache effciency in case the previous block is not executed
+ 	    (so it does not need to be in the cache).
+ 
+ 	 We to catch first case, we align frequently executed blocks.
+ 	 To catch the second, we align blocks that are executed more frequently
+ 	 than the predecesor and the predecesor is likely to not be executed
+ 	 when function is called.  */
+ 
+       if (!has_fallthru
+ 	  && (branch_frequency > BB_FREQ_MAX / 10
+ 	      || (bb->frequency > BASIC_BLOCK (i - 1)->frequency * 10
+ 		  && (BASIC_BLOCK (i - 1)->frequency
+ 		      <= ENTRY_BLOCK_PTR->frequency / 2))))
+ 	{
+ 	  log = JUMP_ALIGN (label);
+ 	  if (max_log < log)
+ 	    {
+ 	      max_log = log;
+ 	      max_skip = JUMP_ALIGN_MAX_SKIP;
+ 	    }
+ 	}
+       /* In case block is frequent and reached mostly by non-fallthru edge,
+ 	 align it.  It is most likely an first block of loop.  */
+       if (has_fallthru
+ 	  && branch_frequency + fallthru_frequency > BB_FREQ_MAX / 10
+ 	  && branch_frequency > fallthru_frequency * 5)
+ 	{
+ 	  log = LOOP_ALIGN (label);
+ 	  if (max_log < log)
+ 	    {
+ 	      max_log = log;
+ 	      max_skip = LOOP_ALIGN_MAX_SKIP;
+ 	    }
+ 	}
+       LABEL_TO_ALIGNMENT (label) = max_log;
+       LABEL_TO_MAX_SKIP (label) = max_skip;
+     }
+ }
+ 
  /* Make a pass over all insns and compute their actual lengths by shortening
     any branches of variable length if possible.  */
  
*************** shorten_branches (first)
*** 972,992 ****
  
  #endif
  
-   /* We must do some computations even when not actually shortening, in
-      order to get the alignment information for the labels.  */
- 
-   init_insn_lengths ();
- 
    /* Compute maximum UID and allocate label_align / uid_shuid.  */
    max_uid = get_max_uid ();
  
-   max_labelno = max_label_num ();
-   min_labelno = get_first_label_num ();
-   label_align = (struct label_alignment *)
-     xcalloc ((max_labelno - min_labelno + 1), sizeof (struct label_alignment));
- 
    uid_shuid = (int *) xmalloc (max_uid * sizeof *uid_shuid);
  
    /* Initialize label_align and set up uid_shuid to be strictly
       monotonically rising with insn order.  */
    /* We use max_log here to keep track of the maximum alignment we want to
--- 1058,1079 ----
  
  #endif
  
    /* Compute maximum UID and allocate label_align / uid_shuid.  */
    max_uid = get_max_uid ();
  
    uid_shuid = (int *) xmalloc (max_uid * sizeof *uid_shuid);
  
+   if (max_labelno != max_label_num ())
+     {
+       int old = max_labelno;
+       max_labelno = max_label_num ();
+       label_align = (struct label_alignment *) xrealloc
+ 	(label_align,
+ 	 (max_labelno - min_labelno + 1) * sizeof (struct label_alignment));
+       memset (label_align + old + 1 - min_labelno, 0,
+ 	      sizeof (struct label_alignment) * (max_labelno - old));
+     }
+ 
    /* Initialize label_align and set up uid_shuid to be strictly
       monotonically rising with insn order.  */
    /* We use max_log here to keep track of the maximum alignment we want to
*************** shorten_branches (first)
*** 1012,1017 ****
--- 1099,1112 ----
        else if (GET_CODE (insn) == CODE_LABEL)
  	{
  	  rtx next;
+ 	  
+ 	  /* Merge in alignments computed by compute_alignments.  */
+ 	  log = LABEL_TO_ALIGNMENT (insn);
+ 	  if (max_log < log)
+ 	    {
+ 	      max_log = log;
+ 	      max_skip = LABEL_TO_MAX_SKIP (insn);
+ 	    }
  
  	  log = LABEL_ALIGN (insn);
  	  if (max_log < log)
*************** shorten_branches (first)
*** 1063,1103 ****
  		break;
  	      }
  	}
-       /* Again, we allow NOTE_INSN_LOOP_BEG - INSN - CODE_LABEL
- 	 sequences in order to handle reorg output efficiently.  */
-       else if (GET_CODE (insn) == NOTE
- 	       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
- 	{
- 	  rtx label;
- 	  int nest = 0;
- 
- 	  /* Search for the label that starts the loop.
- 	     Don't skip past the end of the loop, since that could
- 	     lead to putting an alignment where it does not belong.
- 	     However, a label after a nested (non-)loop would be OK.  */
- 	  for (label = insn; label; label = NEXT_INSN (label))
- 	    {
- 	      if (GET_CODE (label) == NOTE
- 		  && NOTE_LINE_NUMBER (label) == NOTE_INSN_LOOP_BEG)
- 		nest++;
- 	      else if (GET_CODE (label) == NOTE
- 		       && NOTE_LINE_NUMBER (label) == NOTE_INSN_LOOP_END
- 		       && --nest == 0)
- 		break;
- 	      else if (GET_CODE (label) == CODE_LABEL)
- 		{
- 		  log = LOOP_ALIGN (label);
- 		  if (max_log < log)
- 		    {
- 		      max_log = log;
- 		      max_skip = LOOP_ALIGN_MAX_SKIP;
- 		    }
- 		  break;
- 		}
- 	    }
- 	}
-       else
- 	continue;
      }
  #ifdef HAVE_ATTR_length
  
--- 1158,1163 ----
Index: output.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/output.h,v
retrieving revision 1.66
diff -c -3 -p -r1.66 output.h
*** output.h	2001/07/16 06:01:39	1.66
--- output.h	2001/07/29 18:17:13
*************** along with GNU CC; see the file COPYING.
*** 20,25 ****
--- 20,28 ----
  the Free Software Foundation, 59 Temple Place - Suite 330,
  Boston, MA 02111-1307, USA.  */
  
+ /* Compute branch alignments based on frequency information in the CFG.  */
+ extern void compute_alignments  PARAMS ((void));
+ 
  /* Initialize data in final at the beginning of a compilation.  */
  extern void init_final		PARAMS ((const char *));
  
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.500
diff -c -3 -p -r1.500 toplev.c
*** toplev.c	2001/07/26 20:36:01	1.500
--- toplev.c	2001/07/29 18:17:19
*************** rest_of_compilation (decl)
*** 3599,3607 ****
--- 3599,3612 ----
  	  cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_POST_REGSTACK);
  	}
  
+       /* Output final version of CFG.  */
+       if (rtl_dump_file)
+         dump_flow_info (rtl_dump_file);
+ 
        close_dump_file (DFI_bbro, print_rtl_with_bb, insns);
        timevar_pop (TV_REORDER_BLOCKS);
      }
+   compute_alignments ();
  
    /* If a machine dependent reorganization is needed, call it.  */
  #ifdef MACHINE_DEPENDENT_REORG
Index: doc/tm.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/tm.texi,v
retrieving revision 1.39
diff -c -3 -p -r1.39 tm.texi
*** tm.texi	2001/07/23 20:33:40	1.39
--- tm.texi	2001/07/29 18:17:23
*************** the target supports DWARF 2 frame unwind
*** 7121,7130 ****
  This describes commands for alignment.
  
  @table @code
! @findex LABEL_ALIGN_AFTER_BARRIER
! @item LABEL_ALIGN_AFTER_BARRIER (@var{label})
! The alignment (log base 2) to put in front of @var{label}, which follows
! a @code{BARRIER}.
  
  This macro need not be defined if you don't want any special alignment
  to be done at such a time.  Most machine descriptions do not currently
--- 7121,7130 ----
  This describes commands for alignment.
  
  @table @code
! @findex JUMP_ALIGN_AFTER_BARRIER
! @item JUMP_ALIGN (@var{label})
! The alignment (log base 2) to put in front of @var{label}, which is
! a common destination of jumps and has no fallthru incomming edge.
  
  This macro need not be defined if you don't want any special alignment
  to be done at such a time.  Most machine descriptions do not currently
*************** define the macro.
*** 7133,7140 ****
  Unless it's necessary to inspect the @var{label} parameter, it is better
  to set the variable @var{align_jumps} in the target's
  @code{OVERRIDE_OPTIONS}.  Otherwise, you should try to honour the user's
! selection in @var{align_jumps} in a @code{LABEL_ALIGN_AFTER_BARRIER}
! implementation.
  
  @findex LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP
  @item LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP
--- 7133,7149 ----
  Unless it's necessary to inspect the @var{label} parameter, it is better
  to set the variable @var{align_jumps} in the target's
  @code{OVERRIDE_OPTIONS}.  Otherwise, you should try to honour the user's
! selection in @var{align_jumps} in a @code{JUMP_ALIGN} implementation.
! 
! @table @code
! @findex LABEL_ALIGN_AFTER_BARRIER
! @item LABEL_ALIGN_AFTER_BARRIER (@var{label})
! The alignment (log base 2) to put in front of @var{label}, which follows
! a @code{BARRIER}.
! 
! This macro need not be defined if you don't want any special alignment
! to be done at such a time.  Most machine descriptions do not currently
! define the macro.
  
  @findex LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP
  @item LABEL_ALIGN_AFTER_BARRIER_MAX_SKIP


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]