This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
MAINLINE PATCH: Parameterize Delay Slot Compilation
- To: gcc-patches at gcc dot gnu dot org
- Subject: MAINLINE PATCH: Parameterize Delay Slot Compilation
- From: Jeffrey Oldham <oldham at codesourcery dot com>
- Date: Wed, 21 Feb 2001 08:17:20 -0800
- Cc: Jeffrey Oldham <oldham at codesourcery dot com>
- Organization: CodeSourcery LLC
Several quadratic-time algorithms are used to fill delay slots. These
algorithms could be avoided if the control-flow graph information was
maintained during delay slot allocation. In the meantime, we add a
new parameter which converts the O(n*n) techniques to O(100*n)
techniques. This permits many compilations of
gcc.c-torture/compile/20001226-1.c to succeed rather than time out on
mips-sgi-irix6.5, permitting monotonic improvement.
2001-02-21 Jeffrey Oldham <oldham@codesourcery.com>
* Makefile.in (reorg.o): Add params.h dependence.
* params.def: Fix typographical error in comment.
(MAX_DELAY_SLOT_INSN_SEARCH): New parameter.
* params.h: Modify introductory comment.
(MAX_DELAY_SLOT_INSN_SEARCH): New parameter.
* reorg.c: Add dependence on params.h.
(redundant_insn): Add parameterized throttle for search.
(fill_simple_delay_slots): Add a comment explaining a variable.
Move conditional out of loop, simplifying code.
(fill_eager_delay_slots): Fix typographical error in comment.
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.611
diff -c -p -r1.611 Makefile.in
*** Makefile.in 2001/02/19 00:05:49 1.611
--- Makefile.in 2001/02/21 16:04:11
*************** caller-save.o : caller-save.c $(CONFIG_H
*** 1481,1487 ****
$(RECOG_H) reload.h $(EXPR_H) toplev.h
reorg.o : reorg.c $(CONFIG_H) system.h $(RTL_H) conditions.h hard-reg-set.h \
$(BASIC_BLOCK_H) $(REGS_H) insn-config.h $(INSN_ATTR_H) insn-flags.h \
! $(RECOG_H) function.h flags.h output.h $(EXPR_H) toplev.h
alias.o : alias.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h \
$(BASIC_BLOCK_H) $(REGS_H) toplev.h output.h $(EXPR_H) insn-flags.h \
$(GGC_H) function.h cselib.h $(TREE_H)
--- 1481,1487 ----
$(RECOG_H) reload.h $(EXPR_H) toplev.h
reorg.o : reorg.c $(CONFIG_H) system.h $(RTL_H) conditions.h hard-reg-set.h \
$(BASIC_BLOCK_H) $(REGS_H) insn-config.h $(INSN_ATTR_H) insn-flags.h \
! $(RECOG_H) function.h flags.h output.h $(EXPR_H) toplev.h params.h
alias.o : alias.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h \
$(BASIC_BLOCK_H) $(REGS_H) toplev.h output.h $(EXPR_H) insn-flags.h \
$(GGC_H) function.h cselib.h $(TREE_H)
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.1
diff -c -p -r1.1 params.def
*** params.def 2001/02/14 16:24:45 1.1
--- params.def 2001/02/21 16:04:11
*************** Boston, MA 02111-1307, USA.
*** 24,30 ****
/* This file contains definitions for language-independent
parameters. The DEFPARAM macro takes 4 arguments:
! - The enumeral corresonding to this parameter.
- The name that can be used to set this parameter using the
command-line option `--param <name>=<value>'.
--- 24,30 ----
/* This file contains definitions for language-independent
parameters. The DEFPARAM macro takes 4 arguments:
! - The enumeral corresponding to this parameter.
- The name that can be used to set this parameter using the
command-line option `--param <name>=<value>'.
*************** DEFPARAM (PARAM_MAX_INLINE_INSNS,
*** 43,48 ****
--- 43,59 ----
"max-inline-insns",
"The maximum number of instructions in a function that is eligible for inlining",
10000)
+
+ /* The maximum number of instructions to consider when looking for an
+ instruction to fill a delay slot. If more than this arbitrary
+ number of instructions is searched, the time savings from filling
+ the delay slot will be minimal so stop searching. Increasing
+ values mean more aggressive optimization, making the compile time
+ increase with probably small improvement in executable run time. */
+ DEFPARAM (PARAM_MAX_DELAY_SLOT_INSN_SEARCH,
+ "max-delay-slot-insn-search",
+ "The maximum number of instructions to consider to fill a delay slot",
+ 100)
/*
Local variables:
Index: params.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.h,v
retrieving revision 1.1
diff -c -p -r1.1 params.h
*** params.h 2001/02/14 16:24:45 1.1
--- params.h 2001/02/21 16:04:11
*************** Boston, MA 02111-1307, USA.
*** 27,34 ****
place. The values of the parameters can be set on the
command-line, thereby providing a way to control the amount of
effort spent on particular optimization passes, or otherwise tune
! the behavior of the compiler. */
#ifndef PARAMS_H
#define PARAMS_H
--- 27,37 ----
place. The values of the parameters can be set on the
command-line, thereby providing a way to control the amount of
effort spent on particular optimization passes, or otherwise tune
! the behavior of the compiler.
+ Since their values can be set on the command-line, these parameters
+ should not be used for non-dynamic memory allocation. */
+
#ifndef PARAMS_H
#define PARAMS_H
*************** typedef enum compiler_param
*** 81,85 ****
--- 84,90 ----
/* Macros for the various parameters. */
#define MAX_INLINE_INSNS \
PARAM_VALUE (PARAM_MAX_INLINE_INSNS)
+ #define MAX_DELAY_SLOT_INSN_SEARCH \
+ PARAM_VALUE (PARAM_MAX_DELAY_SLOT_INSN_SEARCH)
#endif /* PARAMS_H */
Index: reorg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/reorg.c,v
retrieving revision 1.56
diff -c -p -r1.56 reorg.c
*** reorg.c 2000/11/07 22:49:54 1.56
--- reorg.c 2001/02/21 16:04:11
*************** Boston, MA 02111-1307, USA. */
*** 139,144 ****
--- 139,145 ----
#include "obstack.h"
#include "insn-attr.h"
#include "resource.h"
+ #include "params.h"
#ifdef DELAY_SLOTS
*************** redundant_insn (insn, target, delay_list
*** 1635,1640 ****
--- 1636,1642 ----
rtx trial, pat;
struct resources needed, set;
int i;
+ unsigned insns_to_search;
/* If INSN has any REG_UNUSED notes, it can't match anything since we
are allowed to not actually assign to such a register. */
*************** redundant_insn (insn, target, delay_list
*** 1642,1648 ****
return 0;
/* Scan backwards looking for a match. */
! for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
{
if (GET_CODE (trial) == CODE_LABEL)
return 0;
--- 1644,1653 ----
return 0;
/* Scan backwards looking for a match. */
! for (trial = PREV_INSN (target),
! insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
! trial && insns_to_search > 0;
! trial = PREV_INSN (trial), --insns_to_search)
{
if (GET_CODE (trial) == CODE_LABEL)
return 0;
*************** redundant_insn (insn, target, delay_list
*** 1743,1751 ****
/* Scan backwards until we reach a label or an insn that uses something
INSN sets or sets something insn uses or sets. */
! for (trial = PREV_INSN (target);
! trial && GET_CODE (trial) != CODE_LABEL;
! trial = PREV_INSN (trial))
{
if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
&& GET_CODE (trial) != JUMP_INSN)
--- 1748,1757 ----
/* Scan backwards until we reach a label or an insn that uses something
INSN sets or sets something insn uses or sets. */
! for (trial = PREV_INSN (target),
! insns_to_search = MAX_DELAY_SLOT_INSN_SEARCH;
! trial && GET_CODE (trial) != CODE_LABEL && insns_to_search > 0;
! trial = PREV_INSN (trial), --insns_to_search)
{
if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
&& GET_CODE (trial) != JUMP_INSN)
*************** fill_simple_delay_slots (non_jumps_p)
*** 2223,2231 ****
&& ! simplejump_p (insn)
&& JUMP_LABEL (insn) != 0)))
{
rtx target = 0;
int maybe_never = 0;
! struct resources needed_at_jump;
CLEAR_RESOURCE (&needed);
CLEAR_RESOURCE (&set);
--- 2229,2239 ----
&& ! simplejump_p (insn)
&& JUMP_LABEL (insn) != 0)))
{
+ /* Invariant: If insn is a JUMP_INSN, the insn's jump
+ label. Otherwise, zero. */
rtx target = 0;
int maybe_never = 0;
! rtx pat, trial_delay;
CLEAR_RESOURCE (&needed);
CLEAR_RESOURCE (&set);
*************** fill_simple_delay_slots (non_jumps_p)
*** 2243,2335 ****
if (GET_CODE (insn) == JUMP_INSN)
target = JUMP_LABEL (insn);
}
-
- for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
- {
- rtx pat, trial_delay;
-
- next_trial = next_nonnote_insn (trial);
! if (GET_CODE (trial) == CODE_LABEL
! || GET_CODE (trial) == BARRIER)
! break;
! /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
! pat = PATTERN (trial);
! /* Stand-alone USE and CLOBBER are just for flow. */
! if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
! continue;
!
! /* If this already has filled delay slots, get the insn needing
! the delay slots. */
! if (GET_CODE (pat) == SEQUENCE)
! trial_delay = XVECEXP (pat, 0, 0);
! else
! trial_delay = trial;
!
! /* If this is a jump insn to our target, indicate that we have
! seen another jump to it. If we aren't handling a conditional
! jump, stop our search. Otherwise, compute the needs at its
! target and add them to NEEDED. */
! if (GET_CODE (trial_delay) == JUMP_INSN)
! {
! if (target == 0)
! break;
! else if (JUMP_LABEL (trial_delay) != target)
! {
! rtx ninsn =
! next_active_insn (JUMP_LABEL (trial_delay));
!
! mark_target_live_regs (get_insns (), ninsn,
! &needed_at_jump);
! needed.memory |= needed_at_jump.memory;
! needed.unch_memory |= needed_at_jump.unch_memory;
! IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
! }
! }
! /* See if we have a resource problem before we try to
! split. */
! if (target == 0
! && GET_CODE (pat) != SEQUENCE
! && ! insn_references_resource_p (trial, &set, 1)
! && ! insn_sets_resource_p (trial, &set, 1)
! && ! insn_sets_resource_p (trial, &needed, 1)
#ifdef HAVE_cc0
! && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
#endif
! && ! (maybe_never && may_trap_p (pat))
! && (trial = try_split (pat, trial, 0))
! && eligible_for_delay (insn, slots_filled, trial, flags))
! {
! next_trial = next_nonnote_insn (trial);
! delay_list = add_to_delay_list (trial, delay_list);
#ifdef HAVE_cc0
! if (reg_mentioned_p (cc0_rtx, pat))
! link_cc0_insns (trial);
#endif
! delete_insn (trial);
! if (slots_to_fill == ++slots_filled)
! break;
! continue;
! }
! mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
! mark_referenced_resources (trial, &needed, 1);
! /* Ensure we don't put insns between the setting of cc and the
! comparison by moving a setting of cc into an earlier delay
! slot since these insns could clobber the condition code. */
! set.cc = 1;
!
! /* If this is a call or jump, we might not get here. */
! if (GET_CODE (trial_delay) == CALL_INSN
! || GET_CODE (trial_delay) == JUMP_INSN)
! maybe_never = 1;
! }
/* If there are slots left to fill and our search was stopped by an
unconditional branch, try the insn at the branch target. We can
--- 2251,2324 ----
if (GET_CODE (insn) == JUMP_INSN)
target = JUMP_LABEL (insn);
}
! if (target == 0)
! for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
! {
! next_trial = next_nonnote_insn (trial);
!
! if (GET_CODE (trial) == CODE_LABEL
! || GET_CODE (trial) == BARRIER)
! break;
! /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
! pat = PATTERN (trial);
! /* Stand-alone USE and CLOBBER are just for flow. */
! if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
! continue;
! /* If this already has filled delay slots, get the insn needing
! the delay slots. */
! if (GET_CODE (pat) == SEQUENCE)
! trial_delay = XVECEXP (pat, 0, 0);
! else
! trial_delay = trial;
!
! /* Stop our search when seeing an unconditional jump. */
! if (GET_CODE (trial_delay) == JUMP_INSN)
! break;
!
! /* See if we have a resource problem before we try to
! split. */
! if (GET_CODE (pat) != SEQUENCE
! && ! insn_references_resource_p (trial, &set, 1)
! && ! insn_sets_resource_p (trial, &set, 1)
! && ! insn_sets_resource_p (trial, &needed, 1)
#ifdef HAVE_cc0
! && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
#endif
! && ! (maybe_never && may_trap_p (pat))
! && (trial = try_split (pat, trial, 0))
! && eligible_for_delay (insn, slots_filled, trial, flags))
! {
! next_trial = next_nonnote_insn (trial);
! delay_list = add_to_delay_list (trial, delay_list);
#ifdef HAVE_cc0
! if (reg_mentioned_p (cc0_rtx, pat))
! link_cc0_insns (trial);
#endif
! delete_insn (trial);
! if (slots_to_fill == ++slots_filled)
! break;
! continue;
! }
! mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
! mark_referenced_resources (trial, &needed, 1);
! /* Ensure we don't put insns between the setting of cc and the
! comparison by moving a setting of cc into an earlier delay
! slot since these insns could clobber the condition code. */
! set.cc = 1;
!
! /* If this is a call or jump, we might not get here. */
! if (GET_CODE (trial_delay) == CALL_INSN
! || GET_CODE (trial_delay) == JUMP_INSN)
! maybe_never = 1;
! }
/* If there are slots left to fill and our search was stopped by an
unconditional branch, try the insn at the branch target. We can
*************** fill_eager_delay_slots ()
*** 2982,2988 ****
}
/* If this insn is expected to branch, first try to get insns from our
! target, then our fallthrough insns. If it is not, expected to branch,
try the other order. */
if (prediction > 0)
--- 2971,2977 ----
}
/* If this insn is expected to branch, first try to get insns from our
! target, then our fallthrough insns. If it is not expected to branch,
try the other order. */
if (prediction > 0)