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]

Shorten unnecesarily large alignments



Hi
This patch adds simple pass to shorten_branches to cut large alignments.
It is targeted for Athlon and Pentium CPUs that preffers large alignmetns
(16 and 32 bytes). These alignments are often larger than the loop
they covers and results in unnecesary nops, that hurts especially in
nested loops (matrix multiplication code etc.).

The patch saves about 5% of XaoS binary on -march=pentiumpro
and 1% for -march=pentium and I can measure 1% to 4% speedups
on my testsuite in some tests (qsort, dryrstone, sieve).

Fri Dec 30 11:53:22 CET 1999  Jan Hubicka  <hubicka@freesoft.cz>
	* final.c (shorten_alignments): New function.
	(init_uid_align): Likewise.
	(struct label_alignment): Add new field "last_insn".
	(LABEL_TO_LAST_INSN): New macro.
	(shorten_branches): Remove uid_align initialization code,
	call init_uid_align and shorten, set last_insn field of
	label_alignment structure.

*** final.c.nos	Thu Dec 30 11:50:05 1999
--- final.c	Thu Dec 30 11:51:33 1999
*************** static int final_addr_vec_align PROTO ((
*** 312,317 ****
--- 312,319 ----
  #endif
  static int align_fuzz		PROTO ((rtx, rtx, int, unsigned));
  static void set_label_alignment PROTO ((rtx, int, int));
+ static int shorten_alignments	PROTO ((rtx first));
+ static void init_uid_align 	PROTO ((void));
  
  /* Initialize data in final at the beginning of a compilation.  */
  
*************** int insn_current_align;
*** 655,660 ****
--- 657,664 ----
     comments.  */
  
  struct label_alignment {
+   /* Last insn we want to cover by the alignment.  */
+   rtx last_insn;
    short alignment;
    short max_skip;
  };
*************** static int min_labelno, max_labelno;
*** 854,859 ****
--- 858,866 ----
  #define LABEL_TO_MAX_SKIP(LABEL) \
    (label_align[CODE_LABEL_NUMBER (LABEL) - min_labelno].max_skip)
  
+ #define LABEL_TO_LAST_INSN(LABEL) \
+   (label_align[CODE_LABEL_NUMBER (LABEL) - min_labelno].last_insn)
+ 
  /* For the benefit of port specific code do this also as a function.  */
  int
  label_to_alignment (label)
*************** insn_current_reference_address (branch)
*** 963,968 ****
--- 970,1101 ----
  }
  #endif /* HAVE_ATTR_length */
  
+ #if defined (HAVE_ATTR_length) && defined (ASM_OUTPUT_MAX_SKIP_ALIGN)
+ 
+ /* Shorten alignments, that are longer than size of insn chain they are
+    convering.  */
+ 
+ static int
+ shorten_alignments (first)
+      rtx first;
+ {
+   int knownmaxskip = FUNCTION_BOUNDARY / 8;
+   int knownlog = exact_log2 (knownmaxskip);
+   int changed = 1;
+   int update = 0;
+   rtx insn = first;
+ 
+   /* Even with this iterative aligorithm the time complexity of the function
+      remains linear, since only constant amout of alignments can be nested.  */
+ 
+   while (changed)
+     {
+       knownmaxskip = FUNCTION_BOUNDARY / 8;
+       knownlog = exact_log2 (knownmaxskip);
+       knownmaxskip--;
+       insn = first;
+       changed = 0;
+       while (insn)
+ 	{
+ 	  if (GET_CODE (insn) == CODE_LABEL && LABEL_TO_ALIGNMENT (insn))
+ 	    {
+ 	      int log = LABEL_TO_ALIGNMENT (insn);
+ 	      int maxskip = LABEL_TO_MAX_SKIP (insn);
+ 	      if (!maxskip)
+ 		maxskip = (1 << log) - 1;
+ 
+ 	      /* Check if the alignment isn't completely covered by previous one.
+ 	         If so, we may remove the alignment completely.  */
+ 
+ 	      if (log >= knownlog && maxskip <= knownmaxskip)
+ 		{
+ 		  /* We can safely disable this alignment.
+ 		     Our future transofrmations are not going to disturb this.
+ 		     If we cut the length of previous alignments to given value,
+ 		     under our conservate address calculation we can only decrease
+ 		     the size of given insn chain, so we get correct result.  */
+ 
+ 		  LABEL_TO_ALIGNMENT (insn) = 0;
+ 		  update = 1;
+ 		}
+ 	      else
+ 		{
+ 		  int length = 0;
+ 		  rtx insn2 = NEXT_INSN (insn);
+ 		  rtx last_insn = LABEL_TO_LAST_INSN (insn);
+ 
+ 		  /* Look forward and see if we can shorten this alignment.  */
+ 		  while (length <= maxskip)
+ 		    {
+ 		      if (GET_CODE (insn2) == CODE_LABEL
+ 			  && LABEL_TO_ALIGNMENT (insn2))
+ 			{
+ 			  int maxskip2 = LABEL_TO_MAX_SKIP (insn2);
+ 			  if (!maxskip)
+ 			    length += (1 << LABEL_TO_ALIGNMENT (insn2)) - 1;
+ 			  else
+ 			    length += maxskip2;
+ 			}
+ 		      else
+ 			length += insn_lengths[INSN_UID (insn2)];
+ 		      if (insn2 == last_insn)
+ 			break;
+ 		      insn2 = NEXT_INSN (insn2);
+ 		    }
+ 		  if (length <= maxskip)
+ 		    {
+ 		      if (length <= 1)
+ 			LABEL_TO_ALIGNMENT (insn) = 0;
+ 		      maxskip = LABEL_TO_MAX_SKIP (insn) = length - 1;
+ 		      changed = 1;
+ 		      update = 1;
+ 		    }
+ 		  knownmaxskip = maxskip;
+ 		  knownlog = log;
+ 		}
+ 	    }
+ 	  else
+ 	    knownmaxskip -= insn_lengths[INSN_UID (insn)];
+ 	  insn = NEXT_INSN (insn);
+ 	}
+     }
+   return update;
+ }
+ #endif
+ 
+ /* Initialize uid_align.  We scan instructions
+    from end to start, and keep in align_tab[n] the last seen insn
+    that does an alignment of at least n+1, i.e. the successor
+    in the alignment chain for an insn that does / has a known
+    alignment of n.  */
+ #ifdef HAVE_ATTR_length
+ 
+ #define MAX_CODE_ALIGN 16
+ static void
+ init_uid_align ()
+ {
+   int i;
+   rtx seq;
+   rtx align_tab[MAX_CODE_ALIGN];
+   for (i = MAX_CODE_ALIGN; --i >= 0;)
+     align_tab[i] = NULL_RTX;
+   seq = get_last_insn ();
+   for (; seq; seq = PREV_INSN (seq))
+     {
+       int uid = INSN_UID (seq);
+       int log;
+       log = (GET_CODE (seq) == CODE_LABEL ? LABEL_TO_ALIGNMENT (seq) : 0);
+       uid_align[uid] = align_tab[0];
+       if (log)
+ 	{
+ 	  /* Found an alignment label.  */
+ 	  uid_align[uid] = align_tab[log];
+ 	  for (i = log - 1; i >= 0; i--)
+ 	    align_tab[i] = seq;
+ 	}
+     }
+ }
+ #endif
  /* Set alignment of given INSN (label) to the LOG and MAX_SKIP.
     Choose larger of the two alignments in case alignment is already
     defined.  */
*************** shorten_branches (first)
*** 1016,1029 ****
    int i;
    int barrier;
  #ifdef HAVE_ATTR_length
- #define MAX_CODE_ALIGN 16
-   rtx seq;
    int something_changed = 1;
    char *varying_length;
    rtx body;
    int uid;
    struct loops loops;
-   rtx align_tab[MAX_CODE_ALIGN];
  
    /* In order to make sure that all instructions have valid length info,
       we must split them before we compute the address/length info.  */
--- 1149,1159 ----
*************** shorten_branches (first)
*** 1105,1112 ****
  				       LABEL_ALIGN_MAX_SKIP);
  	      }
  	}
!       else if (GET_CODE (insn) == BARRIER)
! 	barrier = 1;
      }
  
    /* Discover the natural loops and enlarge the alignment
--- 1235,1255 ----
  				       LABEL_ALIGN_MAX_SKIP);
  	      }
  	}
!       if (GET_CODE (insn) == BARRIER || ! NEXT_INSN (insn))
!         {
! 	  rtx x = insn;
! 	  barrier = 1;
! 
! 	  /* Shorten all alignments to the barrier.  */
! 	  if (optimize)
! 	    {
! 	      if (GET_CODE (x) == BARRIER)
! 		x = PREV_INSN (x);
! 	      for (; x && GET_CODE (x) != BARRIER; x = PREV_INSN (x))
! 		if (GET_CODE (x) == CODE_LABEL)
! 		  LABEL_TO_LAST_INSN (x) = insn;
! 	    }
! 	}
      }
  
    /* Discover the natural loops and enlarge the alignment
*************** shorten_branches (first)
*** 1118,1127 ****
--- 1261,1287 ----
  
        for (i = 0; i < loops.num; i++)
  	{
+ 	  int index;
+ 	  int end;
+ 	  int last_shuid;
+ 	  rtx last_insn;
  	  rtx insn = loops.array[i].first_block->head;
+ 
  	  if (GET_CODE (insn) != CODE_LABEL)
  	    abort();
  	  set_label_alignment (insn, LOOP_ALIGN (insn), LOOP_ALIGN_MAX_SKIP);
+ 
+ 	  /* Shorten all alignments inside loop.  */
+ 	  last_insn = loops.array[i].last_block->end;
+ 	  last_shuid = INSN_SHUID (last_insn);
+ 	  end = loops.array[i].last_block->index;
+ 	  for (index = loops.array[i].first_block->index; index <= end; index++)
+ 	    {
+ 	      basic_block bb = BASIC_BLOCK (index);
+ 	      if (GET_CODE (bb->head) == CODE_LABEL
+ 		  && INSN_SHUID (LABEL_TO_LAST_INSN (bb->head)) > last_shuid)
+ 		LABEL_TO_LAST_INSN (bb->head) = last_insn;
+ 	    }
  	}
        flow_loops_free (&loops);
      }
*************** shorten_branches (first)
*** 1138,1161 ****
    varying_length = (char *) xcalloc (max_uid + 1, sizeof (char));
  
    uid_align = (rtx *) xcalloc (max_uid + 1, sizeof *uid_align);
! 
!   for (i = MAX_CODE_ALIGN; --i >= 0; )
!     align_tab[i] = NULL_RTX;
!   seq = get_last_insn ();
!   for (; seq; seq = PREV_INSN (seq))
!     {
!       int uid = INSN_UID (seq);
!       int log;
!       log = (GET_CODE (seq) == CODE_LABEL ? LABEL_TO_ALIGNMENT (seq) : 0);
!       uid_align[uid] = align_tab[0];
!       if (log)
! 	{
! 	  /* Found an alignment label.  */
! 	  uid_align[uid] = align_tab[log];
! 	  for (i = log - 1; i >= 0; i--)
! 	    align_tab[i] = seq;
! 	}
!     }
  
  #ifdef CASE_VECTOR_SHORTEN_MODE
    if (optimize)
--- 1298,1304 ----
    varying_length = (char *) xcalloc (max_uid + 1, sizeof (char));
  
    uid_align = (rtx *) xcalloc (max_uid + 1, sizeof *uid_align);
!   init_uid_align();
  
  #ifdef CASE_VECTOR_SHORTEN_MODE
    if (optimize)
*************** shorten_branches (first)
*** 1313,1318 ****
--- 1456,1469 ----
  #endif
      }
  
+ #if defined (HAVE_ATTR_length) && defined (ASM_OUTPUT_MAX_SKIP_ALIGN)
+   /* Attempt to shorten the MAX_SKIP values in alignments.  It is called here
+      in order to remove unnecesarry alignments.  Another time it is called after
+      shortening is done to shorten the values even more if possible.  */
+   if (optimize && shorten_alignments (first))
+     init_uid_align ();
+ #endif
+ 
    /* Now loop over all the insns finding varying length insns.  For each,
       get the current insn length.  If it has changed, reflect the change.
       When nothing changes for a full pass, we are done.  */
*************** shorten_branches (first)
*** 1526,1531 ****
--- 1677,1687 ----
  	break;
      }
  
+ #if defined (HAVE_ATTR_length) && defined (ASM_OUTPUT_MAX_SKIP_ALIGN)
+   /* Attempt to shorten the MAX_SKIP values in alignments.  */
+   if (optimize)
+     shorten_alignments (first);
+ #endif
    free (varying_length);
  
  #endif /* HAVE_ATTR_length */


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