This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[sel-sched] Use instruction hashes, precompute hard regs data
- From: Andrey Belevantsev <abel at ispras dot ru>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 21 Jun 2007 13:55:03 +0400
- Subject: [sel-sched] Use instruction hashes, precompute hard regs data
Hello,
This patch improves compile times of the selective scheduling in two
aspects. First, we introduce insn hashes and use them for two purposes:
faster comparing of two vinsns and remembering the insns on which an
expression was changed. For the latter task, we were using bitmaps, but
it turned out that this approach is wrong. This is because a remembered
insn could be scheduled, leaving its bookkeeping copies in the
instruction stream, and we should undo transformations on copies instead
of the original insn. But this does not happen because bookkeeping
copies are not remembered. So we use a hash for this purpose, which is
obviously the same for the insn and its copy.
The second part is precomputing information that is needed to find a
valid register for renaming. The original code was taken from
regrename.c, and some of its parts could be computed just once. That
is, for every mode we need to compute registers that are capable of
holding a value of this mode, and for every hard reg we need to know
registers in which it is ok to remove them. For that purpose, we have
per-mode and per-register regsets that save this information once being
computed. These are especially helpful when HARD_REGNO_RENAME_OK is a
heavy operation.
There is a lot more to do about compile time, so more of this is coming
in the near future.
Bootstrapped and tested on ia64, committed to sel-sched branch.
Andrey
2007-06-21 Andrey Belevantsev <abel@ispras.ru>
Implement hashing of vinsns. Precompute some of hard
regs info.
* cse.c (hash_rtx_string): Export.
* sel-sched.c (struct hard_regs_data): New struct.
(sel_all_regs): Rename to regs_ever_used, change to HARD_REG_SET
and move to the above struct. Update all uses.
(sel_hrd): New global variable.
(init_hard_regno_rename, sel_hard_regno_rename_ok,
init_regs_for_mode, init_hard_regs_data): New functions.
(mark_unavailable_hard_regs): Move some code to the above
functions and use them. Return early when a destination
is not a register. Move code dealing with frame pointers
from ...
(choose_best_reg_1): ... here.
(find_best_reg_for_rhs): Tidy comment.
(undo_transformations): Fix comment. Use hashes instead of bitmaps
to determine whether an expr was changed on this insns.
(moveup_set_rhs): Likewise.
(sel_global_init): Call init_hard_regs_data.
* sel-sched-ir.c (sel_hash_rtx): New static function. Adopt from
hash_rtx, tidy. Leave only necessary comments.
(vinsn_init): Use it.
(find_in_hash_vect_1, find_in_hash_vect, insert_in_hash_vect): New
functions.
(vinsns_correlate_as_rhses_p): Use vinsn hashes.
(init_expr, copy_expr, merge_expr_data, clear_expr): Update to use
hash vectors instead of bitmaps.
(sel_bb_head): Check for head being NULL before using it.
(sel_add_or_remove_bb): Disable too expensive check.
* sel-sched-ir.h: Include vecprim.h.
(struct _expr): Change the type of change_on_insns field to a vector.
(struct vinsn_def): New field hash.
(VINSN_HASH): New accessor macro.
(find_in_hash_vect, insert_in_hash_vect): Declare.
* rtl.h (hash_rtx_string): Declare.
* vecprim.h: Define a vector type for unsigned values.
Index: gcc/cse.c
===================================================================
--- gcc/cse.c (revision 125912)
+++ gcc/cse.c (working copy)
@@ -588,7 +588,6 @@ static rtx use_related_value (rtx, struc
static inline unsigned canon_hash (rtx, enum machine_mode);
static inline unsigned safe_hash (rtx, enum machine_mode);
-static unsigned hash_rtx_string (const char *);
static rtx canon_reg (rtx, rtx);
static enum rtx_code find_comparison_args (enum rtx_code, rtx *, rtx *,
@@ -2051,8 +2050,9 @@ use_related_value (rtx x, struct table_e
return plus_constant (q->exp, offset);
}
+
/* Hash a string. Just add its bytes up. */
-static inline unsigned
+unsigned
hash_rtx_string (const char *ps)
{
unsigned hash = 0;
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c (revision 125912)
+++ gcc/sel-sched.c (working copy)
@@ -122,6 +122,39 @@ struct sel_sched_region_2_data_def
int highest_seqno_in_use;
};
typedef struct sel_sched_region_2_data_def *sel_sched_region_2_data_t;
+
+/* This struct contains precomputed hard reg sets that are needed when
+ computing registers available for renaming. */
+struct hard_regs_data
+{
+ /* For every mode, this stores registers available for use with
+ that mode. */
+ HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES];
+
+ /* True when regs_for_mode[mode] is initialized. */
+ bool regs_for_mode_ok[NUM_MACHINE_MODES];
+
+ /* For every register, it has regs that are ok to rename into it.
+ The register in question is always set. If not, this means
+ that the whole set is not computed yet. */
+ HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER];
+
+ /* For every mode, this stores registers not available due to
+ call clobbering. */
+ HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES];
+
+ /* All registers that are used or call used. */
+ HARD_REG_SET regs_ever_used;
+
+#ifdef STACK_REGS
+ /* Stack registers. */
+ HARD_REG_SET stack_regs;
+#endif
+};
+
+/* A global structure that contains the needed information about harg
+ regs. */
+static struct hard_regs_data sel_hrd;
/* True if/when we want to emulate Haifa scheduler in the common code.
@@ -669,6 +702,17 @@ vinsn_writes_one_of_regs_p (vinsn_t vi,
return false;
}
+#if 0
+/* True when expressions of MODE are considered for renaming. */
+static inline bool
+mode_ok_for_rename_p (enum machine_mode mode)
+{
+ enum mode_class class = GET_MODE_CLASS (mode);
+
+ return class == MODE_INT || class == MODE_FLOAT;
+}
+#endif
+
/* Returns register class of the output register in INSN.
Returns NO_REGS for call insns because some targets have constraints on
destination register of a call insn.
@@ -731,6 +775,121 @@ get_reg_class (rtx insn)
return NO_REGS;
}
+/* Calculate HARD_REGNO_RENAME_OK data for REGNO. */
+static void
+init_hard_regno_rename (int regno)
+{
+ int cur_reg;
+
+ SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno);
+
+ for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
+ {
+ /* We are not interested in renaming in other regs. */
+ if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg))
+ continue;
+
+ if (HARD_REGNO_RENAME_OK (regno, cur_reg))
+ SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg);
+ }
+}
+
+/* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs
+ data first. */
+static inline bool
+sel_hard_regno_rename_ok (int from, int to)
+{
+#ifdef HARD_REGNO_RENAME_OK
+ /* Check whether this is all calculated. */
+ if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from))
+ return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
+
+ init_hard_regno_rename (from);
+
+ return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
+#else
+ return true;
+#endif
+}
+
+/* Calculate set of registers that are capable of holding MODE. */
+static void
+init_regs_for_mode (enum machine_mode mode)
+{
+ int cur_reg;
+
+ CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]);
+ CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]);
+
+ for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
+ {
+ int nregs = hard_regno_nregs[cur_reg][mode];
+ int i;
+
+ for (i = nregs - 1; i >= 0; --i)
+ if (fixed_regs[cur_reg + i]
+ || global_regs[cur_reg + i]
+ /* Can't use regs which aren't saved by
+ the prologue. */
+ || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i)
+#ifdef LEAF_REGISTERS
+ /* We can't use a non-leaf register if we're in a
+ leaf function. */
+ || (current_function_is_leaf
+ && !LEAF_REGISTERS[cur_reg + i])
+#endif
+ )
+ break;
+
+ if (i >= 0)
+ continue;
+
+ /* See whether it accepts all modes that occur in
+ original insns. */
+ if (! HARD_REGNO_MODE_OK (cur_reg, mode))
+ continue;
+
+ if (HARD_REGNO_CALL_PART_CLOBBERED (cur_reg, mode))
+ SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode],
+ cur_reg);
+
+ /* If the CUR_REG passed all the checks above,
+ then it's ok. */
+ SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg);
+ }
+
+ sel_hrd.regs_for_mode_ok[mode] = true;
+}
+
+/* Init all register sets gathered in HRD. */
+static void
+init_hard_regs_data (void)
+{
+ int cur_reg = 0;
+ enum machine_mode cur_mode = 0;
+
+ CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used);
+ for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
+ if (regs_ever_live[cur_reg] || call_used_regs[cur_reg])
+ SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg);
+
+ /* Initialize registers that are valid based on mode when this is
+ really needed. */
+ for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++)
+ sel_hrd.regs_for_mode_ok[cur_mode] = false;
+
+ /* Mark that all HARD_REGNO_RENAME_OK is not calculated. */
+ for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
+ CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]);
+
+#ifdef STACK_REGS
+ CLEAR_HARD_REG_SET (sel_hrd.stack_regs);
+
+ for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
+ SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg);
+#endif
+}
+
/* Mark hardware regs in UNAVAILABLE_HARD_REGS that are not suitable
for renaming rhs in INSN due to hardware restrictions (register class,
modes compatibility etc). This doesn't affect original insn's dest reg,
@@ -740,50 +899,70 @@ get_reg_class (rtx insn)
unavailable_hard_regs as well. */
static void
-mark_unavailable_hard_regs (def_t def, HARD_REG_SET *unavailable_hard_regs,
- regset used_regs)
+mark_unavailable_hard_regs (def_t def, HARD_REG_SET *unavailable_hard_regs,
+ regset used_regs ATTRIBUTE_UNUSED)
{
enum machine_mode mode;
enum reg_class cl = NO_REGS;
rtx orig_dest;
- int cur_reg;
+ int cur_reg, regno;
HARD_REG_SET hard_regs_ok;
gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
gcc_assert (unavailable_hard_regs);
orig_dest = SET_DEST (PATTERN (def->orig_insn));
+
+ /* We have decided not to rename 'mem = something;' insns, as 'something'
+ is usually a register. */
+ if (!REG_P (orig_dest))
+ return;
+
+ regno = REGNO (orig_dest);
/* If before reload, don't try to work with pseudos. */
- if (!reload_completed && REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
+ if (!reload_completed && !HARD_REGISTER_NUM_P (regno))
return;
mode = GET_MODE (orig_dest);
- gcc_assert (orig_dest != pc_rtx);
- /* Can't proceed with renaming if the original register
- is one of the fixed_regs, global_regs or frame pointer. */
- if (REG_P (orig_dest) && (fixed_regs[REGNO (orig_dest)]
- || global_regs[REGNO (orig_dest)]
+ /* Stop when mode is not supported for renaming. Also Can't proceed
+ if the original register is one of the fixed_regs, global_regs or
+ frame pointer. */
+ if (fixed_regs[regno]
+ || global_regs[regno]
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- || (frame_pointer_needed
- && REGNO (orig_dest) == HARD_FRAME_POINTER_REGNUM)
+ || (frame_pointer_needed && regno == HARD_FRAME_POINTER_REGNUM)
#else
- || (frame_pointer_needed && REGNO (orig_dest) ==
- FRAME_POINTER_REGNUM)
+ || (frame_pointer_needed && regno == FRAME_POINTER_REGNUM)
#endif
- ))
+ )
{
SET_HARD_REG_SET (*unavailable_hard_regs);
/* Give a chance for original register, if it isn't in used_regs. */
- if (REG_P (orig_dest) && !REGNO_REG_SET_P (used_regs,
- REGNO (orig_dest)))
- CLEAR_HARD_REG_BIT (*unavailable_hard_regs, REGNO (orig_dest));
+ CLEAR_HARD_REG_BIT (*unavailable_hard_regs, regno);
return;
}
+ /* If something allocated on stack in this function, mark frame pointer
+ register unavailable, considering also modes.
+ FIXME: it is enough to do this once per all original defs. */
+ if (frame_pointer_needed)
+ {
+ int i;
+
+ for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;)
+ SET_HARD_REG_BIT (*unavailable_hard_regs, FRAME_POINTER_REGNUM + i);
+
+#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+ for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;)
+ SET_HARD_REG_BIT (*unavailable_hard_regs,
+ HARD_FRAME_POINTER_REGNUM + i);
+#endif
+ }
+
#ifdef STACK_REGS
/* For the stack registers the presence of FIRST_STACK_REG in USED_REGS
is equivalent to as if all stack regs were in this set.
@@ -793,10 +972,7 @@ mark_unavailable_hard_regs (def_t def, H
The HARD_REGNO_RENAME_OK covers other cases in condition below. */
if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG)
&& REGNO_REG_SET_P (used_regs, FIRST_STACK_REG))
- {
- for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
- SET_HARD_REG_BIT (*unavailable_hard_regs, cur_reg);
- }
+ IOR_HARD_REG_SET (*unavailable_hard_regs, sel_hrd.stack_regs);
#endif
/* If there's a call on this path, make regs from call_used_reg_set
@@ -811,92 +987,48 @@ mark_unavailable_hard_regs (def_t def, H
/* Leave regs as 'available' only from the current
register class. */
- if (REG_P (orig_dest))
- {
- cl = get_reg_class (def->orig_insn);
- gcc_assert (cl != NO_REGS);
- IOR_COMPL_HARD_REG_SET (*unavailable_hard_regs, reg_class_contents[cl]);
- }
+ cl = get_reg_class (def->orig_insn);
+ gcc_assert (cl != NO_REGS);
+ IOR_COMPL_HARD_REG_SET (*unavailable_hard_regs, reg_class_contents[cl]);
+
+ if (!sel_hrd.regs_for_mode_ok[mode])
+ init_regs_for_mode (mode);
+ /* Leave only registers available for this mode. */
CLEAR_HARD_REG_SET (hard_regs_ok);
+ IOR_HARD_REG_SET (hard_regs_ok, sel_hrd.regs_for_mode[mode]);
- /* No matter what kind of reg it is if it's original reg and it's available
- from liveness analysis (not present in used_regs set) - add it to
- the 'ok' registers so it bypass these restrictions.
- But it still may appear in unavailable regs (see above). */
- if (REG_P (orig_dest) && !REGNO_REG_SET_P (used_regs, REGNO (orig_dest)))
- SET_HARD_REG_BIT (hard_regs_ok, REGNO (orig_dest));
+ /* Exclude registers that are partially call clobbered. */
+ if (def->crosses_call
+ && ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
+ AND_COMPL_HARD_REG_SET (hard_regs_ok,
+ sel_hrd.regs_for_call_clobbered[mode]);
+ /* Leave only those that are ok to rename. */
for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
{
- int nregs = hard_regno_nregs[cur_reg][mode];
+ int nregs;
int i;
+ if (!TEST_HARD_REG_BIT (hard_regs_ok, cur_reg))
+ continue;
+
+ nregs = hard_regno_nregs[cur_reg][mode];
gcc_assert (nregs > 0);
for (i = nregs - 1; i >= 0; --i)
- {
- if (
- /* If this reg is in USED_REGS, set it also in
- UNAVAILABLE_HARD_REGS. */
- REGNO_REG_SET_P (used_regs, cur_reg + i)
- || fixed_regs[cur_reg + i]
- || global_regs[cur_reg + i]
- /* Can't use regs which aren't saved by
- the prologue. */
- /* FIXME: throwing out this condition may reveal more
- possibilities for renaming, but in this case we'll
- need to set regs_ever_live for that reg and rewrite
- the prologue. Furthermore, when choosing best reg
- among available for renaming we'll need to count
- whether it adds a new reg to the function. */
- /* FIXME: ? this loop can be optimized
- if traversing union of regs_ever_live
- and call_used_regs? */
- || !REGNO_REG_SET_P (sel_all_regs, (cur_reg + i))
-#ifdef LEAF_REGISTERS
- /* We can't use a non-leaf register if we're in a
- leaf function. */
- || (current_function_is_leaf
- && !LEAF_REGISTERS[cur_reg + i])
-#endif
-#ifdef HARD_REGNO_RENAME_OK
- /* Hardware specific registers that
- can't be clobbered. Counts only if the dest
- is a register, cause if it's a MEM, we always
- can store it in register as well (with mode
- restrictions). */
- || (REG_P (orig_dest)
- && !HARD_REGNO_RENAME_OK (
- REGNO (orig_dest)+ i, cur_reg + i))
-#endif
- )
- break;
- }
- if (i >= 0)
- continue;
-
- /* See whether it accepts all modes that occur in
- original insns. */
- if (! HARD_REGNO_MODE_OK (cur_reg, mode)
- || (def->crosses_call
- /* We shouldn't care about call clobberedness
- unless the DST_LOC is a reg.
- Btw HARD_REGNO_CALL_PART_CLOBBERED defined
- to 0 for most platforms including x86 &
- ia64. */
- && (REG_P (orig_dest)
- && !(HARD_REGNO_CALL_PART_CLOBBERED
- (REGNO (orig_dest), mode)))
- && (HARD_REGNO_CALL_PART_CLOBBERED
- (cur_reg, mode))))
- continue;
+ if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i))
+ break;
- /* If the CUR_REG passed all the checks above,
- then it's ok. */
- SET_HARD_REG_BIT (hard_regs_ok, cur_reg);
+ if (i >= 0)
+ CLEAR_HARD_REG_BIT (hard_regs_ok, cur_reg);
}
+ /* Regno is always ok from the renaming part of view, but it really
+ could be in *unavailable_hard_regs already, so set it here instead
+ of there. */
+ SET_HARD_REG_BIT (hard_regs_ok, regno);
+
/* Exclude all hard regs but HARD_REGS_OK. */
IOR_COMPL_HARD_REG_SET (*unavailable_hard_regs, hard_regs_ok);
}
@@ -942,22 +1074,6 @@ choose_best_reg_1 (HARD_REG_SET unavaila
def_list_iterator i;
def_t def;
- /* Don't clobber traceback for noreturn functions. */
- /* If something allocated on stack in this function, mark frame pointer
- register unavailable, considering also modes. */
- if (frame_pointer_needed)
- {
- int i;
-
- for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;)
- SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
-
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;)
- SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i);
-#endif
- }
-
/* If original register is available, return it. */
*is_orig_reg_p_ptr = true;
@@ -1008,12 +1124,6 @@ choose_best_reg_1 (HARD_REG_SET unavaila
return NULL_RTX;
}
-/* A regset that includes all registers that present in current region.
- Used in assertions to check that we don't introduce new registers when
- should not. */
-static regset_head _sel_all_regs;
-regset sel_all_regs = &_sel_all_regs;
-
/* A wrapper around choose_best_reg_1 () to verify that we make correct
assumptions about available registers in the function. */
static rtx
@@ -1024,7 +1134,7 @@ choose_best_reg (HARD_REG_SET unavailabl
is_orig_reg_p_ptr);
gcc_assert (best_reg == NULL_RTX
- || REGNO_REG_SET_P (sel_all_regs, REGNO (best_reg)));
+ || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg)));
return best_reg;
}
@@ -1218,10 +1328,8 @@ find_best_reg_for_rhs (rhs_t rhs, blist_
|| !replace_dest_with_reg_ok_p (def->orig_insn,
best_reg))
{
- /* Insn will be removed from rhs_vliw below. */
- /* FIXME: may be it will work with other regs?
- Not with example above, though - we can't figure
- that the only option is to generate subreg. */
+ /* Insn will be removed from rhs_vliw below.
+ FIXME: may be it will work with other regs? */
reg_ok = false;
break;
}
@@ -1514,7 +1622,8 @@ undo_transformations (av_set_t *av_ptr,
{
av_set_iterator av_iter;
rhs_t rhs;
- av_set_t new_set;
+ unsigned hash;
+ av_set_t new_set = NULL;
/* First, kill any RHS that uses registers set by an insn. This is
required for correctness. */
@@ -1523,7 +1632,7 @@ undo_transformations (av_set_t *av_ptr,
&& bitmap_intersect_p (INSN_REG_SETS (insn),
VINSN_REG_USES (EXPR_VINSN (rhs)))
/* When an insn looks like 'r1 = r1', we could substitute through
- it, but the above condition will still hold. This happend with
+ it, but the above condition will still hold. This happened with
gcc.c-torture/execute/961125-1.c. */
&& !identical_copy_p (insn))
{
@@ -1532,11 +1641,12 @@ undo_transformations (av_set_t *av_ptr,
av_set_iter_remove (&av_iter);
}
- /* FIXME: don't use the tracking bitmaps until we'll be able to use
- vinsn hashes. */
+ hash = VINSN_HASH (INSN_VINSN (insn));
+ /* FIXME: we need to determine whether RHS was changed on this insn
+ just once. */
FOR_EACH_RHS (rhs, av_iter, *av_ptr)
{
- if (1 || bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+ if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0)
un_speculate (rhs, insn);
}
@@ -1544,7 +1654,7 @@ undo_transformations (av_set_t *av_ptr,
FOR_EACH_RHS (rhs, av_iter, *av_ptr)
{
- if (1 || bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+ if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0)
un_substitute (rhs, insn, &new_set);
}
@@ -1562,7 +1672,7 @@ moveup_rhs_inside_insn_group (rhs_t insn
{
vinsn_t vi = RHS_VINSN (insn_to_move_up);
insn_t insn = VINSN_INSN (vi);
- ds_t *has_dep_p;
+ ds_t *has_dep_p;
ds_t full_ds;
full_ds = has_dependence_p (insn_to_move_up, through_insn, &has_dep_p);
@@ -1808,7 +1918,8 @@ moveup_set_rhs (av_set_t *avp, insn_t in
print (" - changed");
/* Mark that this insn changed this expr. */
- bitmap_set_bit (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn));
+ insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (rhs),
+ VINSN_HASH (INSN_VINSN (insn)));
{
rhs_t rhs2 = av_set_lookup_other_equiv_rhs (*avp, RHS_VINSN (rhs));
@@ -5216,26 +5327,15 @@ sel_global_init (void)
sched_rgn_init (flag_sel_sched_single_block_regions != 0,
flag_sel_sched_ebb_regions != 0);
- /* Init the set of all registers available in the function. */
- INIT_REG_SET (sel_all_regs);
-
- {
- int i;
-
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- {
- if (regs_ever_live[i]
- || call_used_regs[i])
- SET_REGNO_REG_SET (sel_all_regs, i);
- }
- }
-
sel_extend_insn_rtx_data ();
-
+
setup_nop_and_exit_insns ();
sel_extend_global_bb_info ();
+
init_lv_sets ();
+
+ init_hard_regs_data ();
}
/* Free the global data of the scheduler. */
@@ -5253,8 +5353,6 @@ sel_global_finish (void)
sel_finish_insn_rtx_data ();
- CLEAR_REG_SET (sel_all_regs);
-
sched_rgn_finish ();
sched_finish_bbs ();
sched_finish ();
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c (revision 125912)
+++ gcc/sel-sched-ir.c (working copy)
@@ -1002,6 +1002,202 @@ sel_rtx_equal_p (rtx x, rtx y)
return 1;
}
+/* Hash an rtx X. The difference from hash_rtx is that we try to hash as
+ much stuff as possible, not skipping volatile mems, calls, etc. */
+
+static unsigned
+sel_hash_rtx (rtx x, enum machine_mode mode)
+{
+ int i, j;
+ unsigned hash = 0;
+ enum rtx_code code;
+ const char *fmt;
+
+ /* Used to turn recursion into iteration. */
+ repeat:
+ if (x == 0)
+ return hash;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case REG:
+ {
+ unsigned int regno = REGNO (x);
+
+ hash += ((unsigned int) REG << 7);
+ hash += regno;
+ return hash;
+ }
+
+ case SUBREG:
+ {
+ if (REG_P (SUBREG_REG (x)))
+ {
+ hash += (((unsigned int) SUBREG << 7)
+ + REGNO (SUBREG_REG (x))
+ + (SUBREG_BYTE (x) / UNITS_PER_WORD));
+ return hash;
+ }
+ break;
+ }
+
+ case CONST_INT:
+ hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
+ + (unsigned int) INTVAL (x));
+ return hash;
+
+ case CONST_DOUBLE:
+ hash += (unsigned int) code + (unsigned int) GET_MODE (x);
+ if (GET_MODE (x) != VOIDmode)
+ hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
+ else
+ hash += ((unsigned int) CONST_DOUBLE_LOW (x)
+ + (unsigned int) CONST_DOUBLE_HIGH (x));
+ return hash;
+
+ case CONST_VECTOR:
+ {
+ int units;
+ rtx elt;
+
+ units = CONST_VECTOR_NUNITS (x);
+
+ for (i = 0; i < units; ++i)
+ {
+ elt = CONST_VECTOR_ELT (x, i);
+ hash += sel_hash_rtx (elt, GET_MODE (elt));
+ }
+
+ return hash;
+ }
+
+ /* Assume there is only one rtx object for any given label. */
+ case LABEL_REF:
+ /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
+ differences and differences between each stage's debugging dumps. */
+ hash += (((unsigned int) LABEL_REF << 7)
+ + CODE_LABEL_NUMBER (XEXP (x, 0)));
+ return hash;
+
+ case SYMBOL_REF:
+ {
+ /* Don't hash on the symbol's address to avoid bootstrap differences.
+ Different hash values may cause expressions to be recorded in
+ different orders and thus different registers to be used in the
+ final assembler. This also avoids differences in the dump files
+ between various stages. */
+ unsigned int h = 0;
+ const unsigned char *p = (const unsigned char *) XSTR (x, 0);
+
+ while (*p)
+ h += (h << 7) + *p++; /* ??? revisit */
+
+ hash += ((unsigned int) SYMBOL_REF << 7) + h;
+ return hash;
+ }
+
+ case MEM:
+ hash += (unsigned) MEM;
+ x = XEXP (x, 0);
+ goto repeat;
+
+ case USE:
+ if (MEM_P (XEXP (x, 0))
+ && ! MEM_VOLATILE_P (XEXP (x, 0)))
+ {
+ hash += (unsigned) USE;
+ x = XEXP (x, 0);
+
+ hash += (unsigned) MEM;
+ x = XEXP (x, 0);
+ goto repeat;
+ }
+ break;
+
+ case UNSPEC:
+ /* Skip UNSPECs when we are so told. */
+ if (targetm.sched.skip_rtx_p && targetm.sched.skip_rtx_p (x))
+ {
+ hash += sel_hash_rtx (XVECEXP (x, 0, 0), 0);
+ return hash;
+ }
+ break;
+
+ case ASM_OPERANDS:
+ /* We don't want to take the filename and line into account. */
+ hash += (unsigned) code + (unsigned) GET_MODE (x)
+ + hash_rtx_string (ASM_OPERANDS_TEMPLATE (x))
+ + hash_rtx_string (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
+ + (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
+
+ if (ASM_OPERANDS_INPUT_LENGTH (x))
+ {
+ for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
+ {
+ hash += (sel_hash_rtx (ASM_OPERANDS_INPUT (x, i),
+ GET_MODE (ASM_OPERANDS_INPUT (x, i)))
+ + hash_rtx_string
+ (ASM_OPERANDS_INPUT_CONSTRAINT (x, i)));
+ }
+
+ hash += hash_rtx_string (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
+ x = ASM_OPERANDS_INPUT (x, 0);
+ mode = GET_MODE (x);
+ goto repeat;
+ }
+
+ return hash;
+
+ default:
+ break;
+ }
+
+ i = GET_RTX_LENGTH (code) - 1;
+ hash += (unsigned) code + (unsigned) GET_MODE (x);
+ fmt = GET_RTX_FORMAT (code);
+ for (; i >= 0; i--)
+ {
+ switch (fmt[i])
+ {
+ case 'e':
+ /* If we are about to do the last recursive call
+ needed at this level, change it into iteration.
+ This function is called enough to be worth it. */
+ if (i == 0)
+ {
+ x = XEXP (x, i);
+ goto repeat;
+ }
+
+ hash += sel_hash_rtx (XEXP (x, i), 0);
+ break;
+
+ case 'E':
+ for (j = 0; j < XVECLEN (x, i); j++)
+ hash += sel_hash_rtx (XVECEXP (x, i, j), 0);
+ break;
+
+ case 's':
+ hash += hash_rtx_string (XSTR (x, i));
+ break;
+
+ case 'i':
+ hash += (unsigned int) XINT (x, i);
+ break;
+
+ case '0': case 't':
+ /* Unused. */
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ return hash;
+}
+
static bool
vinsn_equal_p (vinsn_t vi1, vinsn_t vi2)
{
@@ -1061,7 +1257,17 @@ vinsn_init (vinsn_t vi, insn_t insn, boo
deps_init_id (id, insn, force_unique_p);
VINSN_ID (vi) = id;
+
+ /* Hash vinsn depending on whether it is separable or not. */
+ if (VINSN_SEPARABLE_P (vi))
+ {
+ rtx rhs = VINSN_RHS (vi);
+ VINSN_HASH (vi) = sel_hash_rtx (rhs, GET_MODE (rhs));
+ }
+ else
+ VINSN_HASH (vi) = sel_hash_rtx (VINSN_PATTERN (vi), VOIDmode);
+
VINSN_COUNT (vi) = 0;
{
@@ -1248,6 +1454,85 @@ sel_gen_insn_from_expr_after (rhs_t expr
/* Functions to work with right-hand sides. */
+/* Search for a hash value HASH in a sorted vector VECT and return true
+ when found. Write to INDP the index on which the search has stopped,
+ such that inserting HASH at INDP will retain VECT's sort order. */
+static bool
+find_in_hash_vect_1 (VEC(unsigned, heap) *vect, unsigned hash, int *indp)
+{
+ unsigned *arr;
+ int i, j, len = VEC_length (unsigned, vect);
+
+ if (len == 0)
+ {
+ *indp = 0;
+ return false;
+ }
+
+ arr = VEC_address (unsigned, vect);
+ i = 0, j = len - 1;
+
+ while (i <= j)
+ {
+#if 0
+ int k = (i + j) / 2;
+
+ if (arr[k] == hash)
+ {
+ *indp = k;
+ return true;
+ }
+
+ if (arr[k] < hash)
+ i = k + 1;
+ else
+ j = k - 1;
+#else
+ unsigned ahash = arr[i];
+
+ if (ahash == hash)
+ {
+ *indp = i;
+ return true;
+ }
+ else if (ahash > hash)
+ break;
+ i++;
+#endif
+ }
+
+ *indp = i;
+ return false;
+}
+
+/* Search for a hash value HASH in a sorted vector VECT. Return
+ the position found or -1, if no such value is in vector. */
+int
+find_in_hash_vect (VEC(unsigned, heap) *vect, unsigned hash)
+{
+ int ind;
+
+ if (find_in_hash_vect_1 (vect, hash, &ind))
+ return ind;
+
+ return -1;
+}
+
+/* Insert HASH in a sorted vector pointed to by PVECT, if HASH is
+ not there already. */
+void
+insert_in_hash_vect (VEC (unsigned, heap) **pvect, unsigned hash)
+{
+ VEC(unsigned, heap) *vect = *pvect;
+ int ind;
+
+ if (! find_in_hash_vect_1 (vect, hash, &ind))
+ {
+ VEC_safe_insert (unsigned, heap, vect, ind, hash);
+ *pvect = vect;
+ }
+}
+
/* Compare two vinsns as rhses if possible and as vinsns otherwise. */
bool
vinsns_correlate_as_rhses_p (vinsn_t x, vinsn_t y)
@@ -1258,6 +1543,9 @@ vinsns_correlate_as_rhses_p (vinsn_t x,
if (VINSN_TYPE (x) != VINSN_TYPE (y))
return false;
+ if (VINSN_HASH (x) != VINSN_HASH (y))
+ return false;
+
if (VINSN_SEPARABLE_P (x))
{
/* Compare RHSes of VINSNs. */
@@ -1274,7 +1562,7 @@ vinsns_correlate_as_rhses_p (vinsn_t x,
/* Initialize RHS. */
static void
init_expr (expr_t expr, vinsn_t vi, int spec, int priority, int sched_times,
- ds_t spec_done_ds, ds_t spec_to_check_ds, bitmap changed_on)
+ ds_t spec_done_ds, ds_t spec_to_check_ds, VEC(unsigned, heap) *changed_on)
{
vinsn_attach (vi);
@@ -1288,16 +1576,16 @@ init_expr (expr_t expr, vinsn_t vi, int
if (changed_on)
EXPR_CHANGED_ON_INSNS (expr) = changed_on;
else
- EXPR_CHANGED_ON_INSNS (expr) = BITMAP_ALLOC (NULL);
+ EXPR_CHANGED_ON_INSNS (expr) = NULL;
}
/* Make a copy of the rhs FROM into the rhs TO. */
void
copy_expr (expr_t to, expr_t from)
{
- bitmap temp = BITMAP_ALLOC (NULL);
+ VEC(unsigned, heap) *temp;
- bitmap_copy (temp, EXPR_CHANGED_ON_INSNS (from));
+ temp = VEC_copy (unsigned, heap, EXPR_CHANGED_ON_INSNS (from));
init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_PRIORITY (from),
EXPR_SCHED_TIMES (from), EXPR_SPEC_DONE_DS (from),
EXPR_SPEC_TO_CHECK_DS (from), temp);
@@ -1317,6 +1605,9 @@ copy_expr_onside (expr_t to, expr_t from
void
merge_expr_data (expr_t to, expr_t from)
{
+ int i;
+ unsigned hash;
+
/* For now, we just set the spec of resulting rhs to be minimum of the specs
of merged rhses. */
if (RHS_SPEC (to) > RHS_SPEC (from))
@@ -1332,8 +1623,13 @@ merge_expr_data (expr_t to, expr_t from)
EXPR_SPEC_DONE_DS (from));
EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
- bitmap_ior_into (EXPR_CHANGED_ON_INSNS (to),
- EXPR_CHANGED_ON_INSNS (from));
+
+ /* We keep this vector sorted. */
+ for (i = 0;
+ VEC_iterate (unsigned, EXPR_CHANGED_ON_INSNS (from), i, hash);
+ i++)
+ insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (to), hash);
+
}
/* Merge bits of FROM rhs to TO rhs. Vinsns in the rhses should correlate. */
@@ -1361,7 +1657,7 @@ clear_expr (rhs_t rhs)
{
vinsn_detach (RHS_VINSN (rhs));
RHS_VINSN (rhs) = NULL;
- BITMAP_FREE (EXPR_CHANGED_ON_INSNS (rhs));
+ VEC_free (unsigned, heap, EXPR_CHANGED_ON_INSNS (rhs));
}
@@ -3103,7 +3399,7 @@ sel_bb_head (basic_block bb)
note = bb_note (bb);
head = next_nonnote_insn (note);
- if (BLOCK_FOR_INSN (head) != bb)
+ if (head && BLOCK_FOR_INSN (head) != bb)
head = NULL_RTX;
}
@@ -3804,7 +4100,7 @@ sel_add_or_remove_bb (basic_block bb, in
rgn_setup_region (CONTAINING_RGN (bb->index));
-#ifdef ENABLE_CHECKING
+#if defined ENABLE_CHECKING && 0
/* This check is verifies that all jumps jump where they should.
This code is adopted from flow.c: init_propagate_block_info (). */
{
Index: gcc/sel-sched-ir.h
===================================================================
--- gcc/sel-sched-ir.h (revision 125912)
+++ gcc/sel-sched-ir.h (working copy)
@@ -37,6 +37,7 @@ Software Foundation, 51 Franklin Street,
#include "rtl.h"
#include "ggc.h"
#include "bitmap.h"
+#include "vecprim.h"
#include "sched-int.h"
#include "sched-rgn.h"
#include "cfgloop.h"
@@ -104,9 +105,11 @@ struct _expr
(used only during move_op ()). */
ds_t spec_to_check_ds;
- /* Here an INSN_LUID (insn) bit is set when this expr was changed when
- moving through insn. */
- bitmap changed_on_insns;
+ /* A vector of insn's hashes on which this expr was changed when
+ moving up. We can't use bitmap here, because the recorded insn
+ could be scheduled, and its bookkeeping copies should be checked
+ instead. */
+ VEC(unsigned, heap) *changed_on_insns;
};
typedef struct _expr expr_def;
@@ -513,6 +516,10 @@ struct vinsn_def
/* Its description. */
idata_t id;
+ /* Hash of vinsn. It is computed either from pattern or from rhs using
+ hash_rtx. It is not placed in ID for faster compares. */
+ unsigned hash;
+
/* Smart pointer counter. */
int count;
@@ -529,6 +536,7 @@ struct vinsn_def
#define VINSN_INSN(VI) (VINSN_INSN_RTX (VI))
#define VINSN_ID(VI) ((VI)->id)
+#define VINSN_HASH(VI) ((VI)->hash)
#define VINSN_TYPE(VI) (IDATA_TYPE (VINSN_ID (VI)))
#define VINSN_SEPARABLE_P(VI) (VINSN_TYPE (VI) == SET)
#define VINSN_CLONABLE_P(VI) (VINSN_SEPARABLE_P (VI) || VINSN_TYPE (VI) == USE)
@@ -889,6 +897,8 @@ extern void copy_expr_onside (expr_t, ex
extern void merge_expr_data (expr_t, expr_t);
extern void merge_expr (expr_t, expr_t);
extern void clear_expr (expr_t);
+extern int find_in_hash_vect (VEC(unsigned, heap) *, unsigned);
+extern void insert_in_hash_vect (VEC(unsigned, heap) **, unsigned);
/* Av set functions. */
extern void av_set_add (av_set_t *, rhs_t);
Index: gcc/rtl.h
===================================================================
--- gcc/rtl.h (revision 125912)
+++ gcc/rtl.h (working copy)
@@ -2000,6 +2000,7 @@ extern int delete_trivially_dead_insns (
extern int cse_main (rtx, int);
extern int exp_equiv_p (rtx, rtx, int, bool);
extern unsigned hash_rtx (rtx x, enum machine_mode, int *, int *, bool);
+extern unsigned hash_rtx_string (const char *);
/* In jump.c */
extern int comparison_dominates_p (enum rtx_code, enum rtx_code);
Index: gcc/vecprim.h
===================================================================
--- gcc/vecprim.h (revision 125912)
+++ gcc/vecprim.h (working copy)
@@ -27,4 +27,7 @@ DEF_VEC_ALLOC_I(char,heap);
DEF_VEC_I(int);
DEF_VEC_ALLOC_I(int,heap);
+DEF_VEC_I(unsigned);
+DEF_VEC_ALLOC_I(unsigned,heap);
+
#endif /* GCC_VECPRIM_H */