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]

MAINLINE PATCH: Speed Delay Slot Allocation


A previous patch added a parameter to convert O(n*n) compile-time
delay slot allocation algorithms to O(100*n) time.  We fix a similar
quadratic compile-time algorithm using another parameter.  This slices
the compilation time of
gcc/testsuite/gcc.c-torture/compile/20001226-1.c on Irix in half.

When delay slot allocation is rewritten to maintain control-flow
information, this change should be eliminated and this test case will
compile in a few seconds, not a few minutes.

2001-02-23  Jeffrey Oldham  <oldham@codesourcery.com>

        * Makefile.in (resource.o): Add params.h dependence.
        * params.def (MAX_DELAY_SLOT_LIVE_SEARCH): New parameter.
        * params.h (MAX_DELAY_SLOT_LIVE_SEARCH): Likewise.
        * resource.c: Add dependence on params.h.
        (current_live_regs): Fix explanatory comment.
        (find_basic_block): Add new parameter to permit limiting search
        for a BARRIER.
        (mark_target_live_regs): Add new argument to find_basic_block call.
        (incr_ticks_for_insn): Likewise.

Tested on       mips-sgi-irix6.5
Approved by     Mark Mitchell (mark@codesourcery.com

Thanks,
Jeffrey D. Oldham
oldham@codesourcery.com
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.612
diff -c -p -r1.612 Makefile.in
*** Makefile.in	2001/02/21 16:11:57	1.612
--- Makefile.in	2001/02/22 17:03:16
*************** sibcall.o : sibcall.c $(CONFIG_H) system
*** 1429,1435 ****
     hard-reg-set.h flags.h insn-config.h $(RECOG_H) $(BASIC_BLOCK_H)
  resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h system.h \
     $(BASIC_BLOCK_H) $(REGS_H) flags.h output.h resource.h function.h toplev.h \
!    $(INSN_ATTR_H) except.h
  lcm.o : lcm.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
     real.h insn-config.h $(INSN_ATTR_H) $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H)
  ssa.o : ssa.c $(CONFIG_H) system.h $(REGS_H) varray.h			\
--- 1429,1435 ----
     hard-reg-set.h flags.h insn-config.h $(RECOG_H) $(BASIC_BLOCK_H)
  resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h system.h \
     $(BASIC_BLOCK_H) $(REGS_H) flags.h output.h resource.h function.h toplev.h \
!    $(INSN_ATTR_H) except.h params.h
  lcm.o : lcm.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
     real.h insn-config.h $(INSN_ATTR_H) $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H)
  ssa.o : ssa.c $(CONFIG_H) system.h $(REGS_H) varray.h			\
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.2
diff -c -p -r1.2 params.def
*** params.def	2001/02/21 16:11:59	1.2
--- params.def	2001/02/22 17:03:16
*************** DEFPARAM (PARAM_MAX_DELAY_SLOT_INSN_SEAR
*** 55,60 ****
--- 55,71 ----
  	  "The maximum number of instructions to consider to fill a delay slot",
  	  100)
  
+ /* When trying to fill delay slots, the maximum number of instructions
+    to consider when searching for a block with valid live register
+    information.  Increasing this arbitrarily chosen value means more
+    aggressive optimization, increasing the compile time.  This
+    parameter should be removed when the delay slot code is rewritten
+    to maintain the control-flow graph.  */
+ DEFPARAM(PARAM_MAX_DELAY_SLOT_LIVE_SEARCH,
+ 	 "max-delay-slot-live-search",
+ 	 "The maximum number of instructions to consider to find accurate live register information",
+ 	 333)
+ 
  /*
  Local variables:
  mode:c
Index: params.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.h,v
retrieving revision 1.2
diff -c -p -r1.2 params.h
*** params.h	2001/02/21 16:11:59	1.2
--- params.h	2001/02/22 17:03:16
*************** typedef enum compiler_param
*** 86,90 ****
--- 86,92 ----
    PARAM_VALUE (PARAM_MAX_INLINE_INSNS)
  #define MAX_DELAY_SLOT_INSN_SEARCH \
    PARAM_VALUE (PARAM_MAX_DELAY_SLOT_INSN_SEARCH)
+ #define MAX_DELAY_SLOT_LIVE_SEARCH \
+   PARAM_VALUE (PARAM_MAX_DELAY_SLOT_LIVE_SEARCH)
  
  #endif /* PARAMS_H */
Index: resource.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/resource.c,v
retrieving revision 1.39
diff -c -p -r1.39 resource.c
*** resource.c	2001/02/16 17:04:36	1.39
--- resource.c	2001/02/22 17:03:17
*************** Boston, MA 02111-1307, USA.  */
*** 32,37 ****
--- 32,38 ----
  #include "resource.h"
  #include "except.h"
  #include "insn-attr.h"
+ #include "params.h"
  
  /* This structure is used to record liveness information at the targets or
     fallthrough insns of branches.  We will most likely need the information
*************** static struct target_info **target_hash_
*** 66,72 ****
  static int *bb_ticks;
  
  /* Marks registers possibly live at the current place being scanned by
!    mark_target_live_regs.  Used only by next two function.    */
  
  static HARD_REG_SET current_live_regs;
  
--- 67,73 ----
  static int *bb_ticks;
  
  /* Marks registers possibly live at the current place being scanned by
!    mark_target_live_regs.  Also used by update_live_status.  */
  
  static HARD_REG_SET current_live_regs;
  
*************** static HARD_REG_SET current_live_regs;
*** 76,82 ****
  static HARD_REG_SET pending_dead_regs;
  
  static void update_live_status		PARAMS ((rtx, rtx, void *));
! static int find_basic_block		PARAMS ((rtx));
  static rtx next_insn_no_annul		PARAMS ((rtx));
  static rtx find_dead_or_set_registers	PARAMS ((rtx, struct resources*,
  						rtx*, int, struct resources,
--- 77,83 ----
  static HARD_REG_SET pending_dead_regs;
  
  static void update_live_status		PARAMS ((rtx, rtx, void *));
! static int find_basic_block		PARAMS ((rtx, int));
  static rtx next_insn_no_annul		PARAMS ((rtx));
  static rtx find_dead_or_set_registers	PARAMS ((rtx, struct resources*,
  						rtx*, int, struct resources,
*************** update_live_status (dest, x, data)
*** 115,139 ****
  	CLEAR_HARD_REG_BIT (pending_dead_regs, i);
        }
  }
- /* Find the number of the basic block that starts closest to INSN.  Return -1
-    if we couldn't find such a basic block.  */
  
  static int
! find_basic_block (insn)
       rtx insn;
  {
    int i;
  
    /* Scan backwards to the previous BARRIER.  Then see if we can find a
       label that starts a basic block.  Return the basic block number.  */
- 
    for (insn = prev_nonnote_insn (insn);
!        insn && GET_CODE (insn) != BARRIER;
!        insn = prev_nonnote_insn (insn))
      ;
  
    /* The start of the function is basic block zero.  */
!   if (insn == 0)
      return 0;
  
    /* See if any of the upcoming CODE_LABELs start a basic block.  If we reach
--- 116,153 ----
  	CLEAR_HARD_REG_BIT (pending_dead_regs, i);
        }
  }
  
+ /* Find the number of the basic block with correct live register
+    information that starts closest to INSN.  Return -1 if we couldn't
+    find such a basic block or the beginning is more than
+    SEARCH_LIMIT instructions before INSN.  Use SEARCH_LIMIT = -1 for
+    an unlimited search.
+ 
+    The delay slot filling code destroys the control-flow graph so,
+    instead of finding the basic block containing INSN, we search
+    backwards toward a BARRIER where the live register information is
+    correct.  */
+ 
  static int
! find_basic_block (insn, search_limit)
       rtx insn;
+      int search_limit;
  {
    int i;
  
    /* Scan backwards to the previous BARRIER.  Then see if we can find a
       label that starts a basic block.  Return the basic block number.  */
    for (insn = prev_nonnote_insn (insn);
!        insn && GET_CODE (insn) != BARRIER && search_limit != 0;
!        insn = prev_nonnote_insn (insn), --search_limit)
      ;
  
+   /* The closest BARRIER is too far away.  */
+   if (search_limit == 0)
+     return -1;
+ 
    /* The start of the function is basic block zero.  */
!   else if (insn == 0)
      return 0;
  
    /* See if any of the upcoming CODE_LABELs start a basic block.  If we reach
*************** mark_target_live_regs (insns, target, re
*** 925,931 ****
      }
  
    if (b == -1)
!     b = find_basic_block (target);
  
    if (target_hash_table != NULL)
      {
--- 939,945 ----
      }
  
    if (b == -1)
!     b = find_basic_block (target, MAX_DELAY_SLOT_LIVE_SEARCH);
  
    if (target_hash_table != NULL)
      {
*************** void
*** 1294,1300 ****
  incr_ticks_for_insn (insn)
       rtx insn;
  {
!   int b = find_basic_block (insn);
  
    if (b != -1)
      bb_ticks[b]++;
--- 1308,1314 ----
  incr_ticks_for_insn (insn)
       rtx insn;
  {
!   int b = find_basic_block (insn, MAX_DELAY_SLOT_LIVE_SEARCH);
  
    if (b != -1)
      bb_ticks[b]++;

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