Autoincrement examples
Joern Rennecke
amylaar@cygnus.co.uk
Thu Nov 18 14:29:00 GMT 1999
> Joern -- can you get a patch for the regmove changes put together and submit
> it to the list?
These are the regmove patches:
Wed Oct 20 20:45:45 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (invalidate_related): New Argument call_tally.
Set rel->reg_orig_calls_crossed when setting rel->invalidate_luid.
Changed all callers.
(optimize_related_values_1): Don't set rel->reg_orig_calls_crossed
if rel->invalidate_luid is set.
(optimize_related_values): Bump CALL_TALLY *after* inputs have
been processed.
(find_related): When recursively processing a SET_DEST of a
CALL_INSN, pass an incremented value for CALL_TALLY.
Wed Oct 20 00:58:08 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (find_related): Ignore registers that change size.
Fri Oct 1 15:04:25 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values_1): Fix check when to
preserve update->insn.
Tue Jun 29 07:46:53 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values_1): When deciding whether to
add a REG_DEAD or REG_UNUSED note, also check for a REG_INC notes
we might have created.
* integrate.c (copy_rtx_and_substitute): Handle NOTE_INSN_DELETED_LABEL
notes. Don't handle 'n' rtx_format case.
Mon Mar 8 16:00:35 1999 Jim Wilson <wilson@cygnus.com>
* regmove.c (optimize_related_values): Add bounds check for b before
BLOCK_HEAD check.
Fri Feb 19 23:10:32 1999 Richard Henderson <rth@cygnus.com>
* regmove.c (optimize_related_values): Use insn modes rather than
sets_cc0_p. Watch basic block heads and ends rather than insn types.
Thu Jan 28 01:08:31 1999 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (find_related): Check if a register belonging to a set
of related values is clobbered in an insn where it is also used.
(optimize_related_values_1): Handle REG_UNUSED notes.
(optimize_related_values): Likewise.
Mon Dec 14 17:08:17 1998 Jim Wilson <wilson@cygnus.com>
* regmove.c (REL_USE_HASH): Use unsigned HOST_WIDE_INT instead of
unsigned.
Fri Nov 13 10:14:04 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values_1): Reject optimization if
offset for rel_base_reg_user would be to large.
Fri Nov 13 04:36:06 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (rel_record_mem): Don't do anything if the register
already has an invalidate_luid.
Thu Nov 12 23:02:32 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (invalidate_related): Don't do anything if the register
already has an invalidate_luid.
(optimize_related_values): Don't update death field if
invalidate_luid field is set.
Wed Oct 14 21:38:11 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values): Check if cc0 is set.
* regmove.c (optimize_related_values): Fix problem with multiple
related values in single insn.
Wed Sep 23 20:42:54 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values_1): Set use->insn when emitting
the linking insn before the final 'use' for a register that does not
die within the scope of the optimization.
Mon Sep 21 15:04:16 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (count_sets): New function.
(gen_add3_insn): If single instruction add fails and source and
destination register are different, try a move / add sequence.
(rel_use_chain): New member match_offset.
(optimize_related_values_1): Set it, and use it to avoid linking
chains when this requires more than one instruction for the add.
(add_limits): New file scope array.
(optimize_related_values): Initialize it.
Mon Sep 21 14:55:36 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* regmove.c (optimize_related_values_1): Don't use rel_base->reg
for a chain that needs an out-of-range offset.
Take setting of rel_base_reg_user into account when deciding
if there are enough registers available.
Tue Sep 15 16:41:00 1998 Michael Tiemann <michael@impact.tiemann.org>
* regmove.c (find_related): We also have to track expressions that
are just naked registers. Otherwise, we burn one register to
prime the related values, and we'll also miss the second (but not
subsequent) opportunities to use related values.
Thu Sep 3 23:33:57 1998 J"orn Rennecke <amylaar@cygnus.co.uk>
* rtl.h (push_obstacks_nochange, end_temporary_allocation): Declare.
* regmove.c (obstack.h): Include.
(REL_USE_HASH_SIZE, REL_USE_HASH, rel_alloc, rel_new): Define.
(struct related, struct related_baseinfo, struct update): New structs.
(struct rel_use_chain, struct rel_use): Likewise.
(regno_related, rel_base_list, unrelatedly_used): New variables.
(related_obstack): Likewise.
(regclass_compatible_p, lookup_related): New functions.
(rel_build_chain, rel_record_mem, invalidate_related): Likewise.
(find_related, chain_starts_earlier, chain_ends_later): Likewise.
(optimize_related_values_1, optimize_related_values_0): Likewise.
(optimize_related_values): Likewise.
(regmove_optimize): Use regclass_compatible_p.
Call optimize_related_values.
Index: regmove.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/regmove.c,v
retrieving revision 1.74
diff -p -r1.74 regmove.c
*** regmove.c 1999/11/08 04:56:18 1.74
--- regmove.c 1999/11/18 22:21:46
*************** Boston, MA 02111-1307, USA. */
*** 40,45 ****
--- 40,46 ----
#include "insn-flags.h"
#include "basic-block.h"
#include "toplev.h"
+ #include "obstack.h"
static int optimize_reg_copy_1 PROTO((rtx, rtx, rtx));
static void optimize_reg_copy_2 PROTO((rtx, rtx, rtx));
*************** static int fixup_match_1 PROTO((rtx, rtx
*** 66,71 ****
--- 67,87 ----
static int reg_is_remote_constant_p PROTO((rtx, rtx, rtx));
static int stable_and_no_regs_but_for_p PROTO((rtx, rtx, rtx));
static int regclass_compatible_p PROTO((int, int));
+ #ifdef AUTO_INC_DEC
+ static struct rel_use *lookup_related PROTO((int, enum reg_class, HOST_WIDE_INT));
+ static void rel_build_chain PROTO((struct rel_use *, struct rel_use *, int));
+ static void rel_record_mem PROTO((rtx *, rtx, int, int, int, rtx, int, int));
+ static void invalidate_related PROTO((rtx, int, int));
+ static void find_related PROTO((rtx *, rtx, int, int));
+ static int chain_starts_earlier PROTO((const PTR, const PTR));
+ static int chain_ends_later PROTO((const PTR, const PTR));
+ static struct related *optimize_related_values_1 PROTO((struct related *, int,
+ int, rtx, FILE *));
+ static void optimize_related_values_0 PROTO((struct related *, int, int,
+ rtx, FILE *));
+ static void optimize_related_values PROTO((int, FILE *));
+ static void count_sets PROTO((rtx, rtx, void *));
+ #endif /* AUTO_INC_DEC */
static int replacement_quality PROTO((rtx));
static int fixup_match_2 PROTO((rtx, rtx, rtx, rtx, FILE *));
static int loop_depth;
*************** gen_add3_insn (r0, r1, c)
*** 90,106 ****
rtx r0, r1, c;
{
int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
! if (icode == CODE_FOR_nothing
|| ! ((*insn_data[icode].operand[0].predicate)
! (r0, insn_data[icode].operand[0].mode))
|| ! ((*insn_data[icode].operand[1].predicate)
! (r1, insn_data[icode].operand[1].mode))
|| ! ((*insn_data[icode].operand[2].predicate)
! (c, insn_data[icode].operand[2].mode)))
return NULL_RTX;
! return (GEN_FCN (icode) (r0, r1, c));
}
--- 106,144 ----
rtx r0, r1, c;
{
int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
+ int mcode;
+ rtx s, move;
! if (icode == CODE_FOR_nothing
|| ! ((*insn_data[icode].operand[0].predicate)
! (r0, insn_data[icode].operand[0].mode)))
! return NULL_RTX;
!
! if (((*insn_data[icode].operand[1].predicate)
! (r1, insn_data[icode].operand[1].mode))
! && ((*insn_data[icode].operand[2].predicate)
! (c, insn_data[icode].operand[2].mode)))
! return (GEN_FCN (icode) (r0, r1, c));
!
! mcode = (int) mov_optab->handlers[(int) GET_MODE (r0)].insn_code;
! if (REGNO (r0) == REGNO (r1)
|| ! ((*insn_data[icode].operand[1].predicate)
! (r0, insn_data[icode].operand[1].mode))
|| ! ((*insn_data[icode].operand[2].predicate)
! (r1, insn_data[icode].operand[2].mode))
! || ! ((*insn_data[mcode].operand[0].predicate)
! (r0, insn_data[mcode].operand[0].mode))
! || ! ((*insn_data[mcode].operand[1].predicate)
! (c, insn_data[mcode].operand[1].mode)))
return NULL_RTX;
! start_sequence ();
! move = emit_insn (GEN_FCN (mcode) (r0, c));
! REG_NOTES (move) = gen_rtx_EXPR_LIST (REG_EQUAL, c, NULL_RTX);
! emit_insn (GEN_FCN (icode) (r0, r0, r1));
! s = gen_sequence ();
! end_sequence ();
! return s;
}
*************** flags_set_1 (x, pat, data)
*** 330,336 ****
&& reg_overlap_mentioned_p (x, flags_set_1_rtx))
flags_set_1_set = 1;
}
!
static int *regno_src_regno;
/* Indicate how good a choice REG (which appears as a source) is to replace
--- 368,1989 ----
&& reg_overlap_mentioned_p (x, flags_set_1_rtx))
flags_set_1_set = 1;
}
!
! #ifdef AUTO_INC_DEC
!
! /* Some machines have two-address-adds and instructions that can
! use only register-indirect addressing and auto_increment, but no
! offsets. If multiple fields of a struct are accessed more than
! once, cse will load each of the member addresses in separate registers.
! This not only costs a lot of registers, but also of instructions,
! since each add to initialize an address register must be really expanded
! into a register-register move followed by an add.
! regmove_optimize uses some heuristics to detect this case; if these
! indicate that this is likely, optimize_related_values is run once for
! the entire function.
!
! We build chains of uses of related values that can be satisfied with the
! same base register by taking advantage of auto-increment address modes
! instead of explicit add instructions.
!
! We try to link chains with disjoint lifetimes together to reduce the
! number of temporary registers and register-register copies.
!
! This optimization pass operates on basic blocks one at a time; it could be
! extended to work on extended basic blocks or entire functions. */
!
! /* For each set of values related to a common base register, we use a
! hash table which maps constant offsets to instructions.
!
! The instructions mapped to are those that use a register which may,
! (possibly with a change in addressing mode) differ from the initial
! value of the base register by exactly that offset after the
! execution of the instruction.
! Here we define the size of the hash table, and the hash function to use. */
! #define REL_USE_HASH_SIZE 43
! #define REL_USE_HASH(I) ((I) % (unsigned HOST_WIDE_INT) REL_USE_HASH_SIZE)
!
! /* For each register in a set of registers that are related, we keep a
! struct related.
!
! u.base contains the register number of the base register (i.e. the one
! that was the source of the first three-address add for this set of
! related values).
!
! INSN is the instruction that initialized the register, or, for the
! base, the instruction that initialized the first non-base register.
!
! BASE is the register number of the base register.
!
! For the base register only, the member BASEINFO points to some extra data.
!
! 'luid' here means linear uid. We count them starting at the function
! start; they are used to avoid overlapping lifetimes.
!
! UPDATES is a list of instructions that set the register to a new
! value that is still related to the same base.
!
! When a register in a set of related values is set to something that
! is not related to the base, INVALIDATE_LUID is set to the luid of
! the instruction that does this set. This is used to avoid re-using
! this register in an overlapping liftime for a related value.
!
! DEATH is first used to store the insn (if any) where the register dies.
! When the optimization is actually performed, the REG_DEAD note from
! the insn denoted by DEATH is removed.
! Thereafter, the removed death note is stored in DEATH, marking not
! only that the register dies, but also making the note available for reuse.
!
! We also use a struct related to keep track of registers that have been
! used for anything that we don't recognize as related values.
! The only really interesting datum for these is u.last_luid, which is
! the luid of the last reference we have seen. These struct relateds
! are marked by a zero INSN field; most other members are not used and
! remain uninitialized. */
!
! struct related {
! rtx insn, reg;
! union { int base; int last_luid; } u;
! HOST_WIDE_INT offset;
! struct related *prev;
! struct update *updates;
! struct related_baseinfo *baseinfo;
! int invalidate_luid;
! rtx death;
! int reg_orig_calls_crossed, reg_set_call_tally, reg_orig_refs;
! };
!
! /* HASHTAB maps offsets to register uses with a matching MATCH_OFFSET.
! PREV_BASE points to the struct related for the previous base register
! that we currently keep track of.
! INSN_LUID is the luid of the instruction that started this set of
! related values. */
! struct related_baseinfo {
! struct rel_use *hashtab[REL_USE_HASH_SIZE];
! struct rel_use_chain *chains;
! struct related *prev_base;
! int insn_luid;
! };
!
! /* INSN is an instruction that sets a register that previously contained
! a related value to a new value that is related to the same base register.
! When the optimization is performed, we have to delete INSN.
! DEATH_INSN points to the insn (if any) where the register died that we
! set in INSN. When we perform the optimization, the REG_DEAD note has
! to be removed from DEATH_INSN.
! PREV points to the struct update that pertains to the previous
! instruction pertaining to the same register that set it from one
! related value to another one. */
! struct update
! {
! rtx insn, death_insn;
! struct update *prev;
! };
!
! struct rel_use_chain
! {
! struct rel_use *chain; /* Points to first use in this chain. */
! struct rel_use_chain *prev, *linked;
! /* Only set after the chain has been completed: */
! struct rel_use *end; /* Last use in this chain. */
! int start_luid, end_luid, calls_crossed;
! rtx reg; /* The register allocated for this chain. */
! HOST_WIDE_INT match_offset; /* Offset after execution of last insn. */
! };
!
! /* ADDRP points to the place where the actual use of the related value is.
! This is commonly a memory address, and has to be set to a register
! or some auto_inc addressing of this register.
! But ADDRP is also used for all other uses of related values to
! the place where the register is inserted; we can tell that an
! unardorned register is to be inserted because no offset adjustment
! is required, hence this is handled by the same logic as register-indirect
! addressing. The only exception to this is when SET_IN_PARALLEL is set,
! see below.
! OFFSET is the offset that is actually used in this instance, i.e.
! the value of the base register when the set of related values was
! created plus OFFSET yields the value that is used.
! This might be different from the value of the used register before
! executing INSN if we elected to use pre-{in,de}crement addressing.
! If we have the option to use post-{in,d})crement addressing, all
! choices are linked cyclically together with the SIBLING field.
! Otherwise, it's a one-link-cycle, i.e. SIBLING points at the
! struct rel_use it is a member of.
! MATCH_OFFSET is the offset that is available after the execution
! of INSN. It is the same as OFFSET for straight register-indirect
! addressing and for pre-{in,de}crement addressing, while it differs
! for the post-{in,de}crement addressing modes.
! If SET_IN_PARALLEL is set, MATCH_OFFSET differs from OFFSET, yet
! this is no post-{in,de}crement addresing. Rather, it is a set
! inside a PARALLEL that adds some constant to a register that holds
! one value of a set of related values that we keep track of.
! ADDRP then points only to the set destination of this set; another
! struct rel_use is used for the source of the set.
! NO_LINK_PRED is nonzero for the last use in a chain if it cannot be
! the predecessor for a another chain to be linked to. This can happen
! for uses that come with a clobber, and for uses by a register that
! is live at the end of the processed range of insns
! (usually a basic block). */
! struct rel_use
! {
! rtx insn, *addrp;
! int luid, call_tally;
! enum reg_class class;
! unsigned set_in_parallel : 1;
! unsigned no_link_pred: 1;
! HOST_WIDE_INT offset, match_offset;
! struct rel_use *next_chain, **prev_chain_ref, *next_hash, *sibling;
! };
!
! struct related **regno_related, *rel_base_list, *unrelatedly_used;
!
! #define rel_alloc(N) obstack_alloc(&related_obstack, (N))
! #define rel_new(X) ((X) = rel_alloc (sizeof *(X)))
!
! static struct obstack related_obstack;
!
! /* For each integer machine mode, the minimum and maximum constant that
! can be added with a single constant.
! This is supposed to define an interval around zero; if there are
! singular points disconnected from this interval, we want to leave
! them out. */
!
! static HOST_WIDE_INT add_limits[NUM_MACHINE_MODES][2];
!
! /* Try to find a related value with offset OFFSET from the base
! register belonging to REGNO, using a register with preferred class
! that is compatible with CLASS. */
! static struct rel_use *
! lookup_related (regno, class, offset)
! int regno;
! enum reg_class class;
! HOST_WIDE_INT offset;
! {
! int base = regno_related[regno]->u.base;
! int hash = REL_USE_HASH (offset);
! struct rel_use *match = regno_related[base]->baseinfo->hashtab[hash];
! for (; match; match = match->next_hash)
! {
! if (offset != match->match_offset)
! continue;
! if (match->next_chain)
! continue;
! if (regclass_compatible_p (class, match->class))
! break;
! }
! return match;
! }
!
! /* Add NEW_USE at the end of the chain that currently ends with MATCH;
! If MATCH is not set, create a new chain.
! BASE is the base register number the chain belongs to. */
! static void
! rel_build_chain (new_use, match, base)
! struct rel_use *new_use, *match;
! int base;
! {
! int hash;
!
! if (match)
! {
! struct rel_use *sibling = match;
! do
! {
! sibling->next_chain = new_use;
! if (sibling->prev_chain_ref)
! *sibling->prev_chain_ref = match;
! sibling = sibling->sibling;
! }
! while (sibling != match);
! new_use->prev_chain_ref = &match->next_chain;
! new_use->next_chain = 0;
! }
! else
! {
! struct rel_use_chain *new_chain;
!
! rel_new (new_chain);
! new_chain->chain = new_use;
! new_use->prev_chain_ref = &new_chain->chain;
! new_use->next_chain = 0;
! new_use->next_chain = NULL_PTR;
! new_chain->linked = 0;
! new_chain->prev = regno_related[base]->baseinfo->chains;
! regno_related[base]->baseinfo->chains = new_chain;
! }
! hash = REL_USE_HASH (new_use->offset);
! new_use->next_hash = regno_related[base]->baseinfo->hashtab[hash];
! regno_related[base]->baseinfo->hashtab[hash] = new_use;
! }
!
! /* Record the use of register ADDR in a memory reference.
! ADDRP is the memory location where the address is stored.
! SIZE is the size of the memory reference.
! PRE_OFFS is the offset that has to be added to the value in ADDR
! due to PRE_{IN,DE}CREMENT addressing in the original address; likewise,
! POST_OFFSET denotes POST_{IN,DE}CREMENT addressing. INSN is the
! instruction that uses this address, LUID its luid, and CALL_TALLY
! the current number of calls encountered since the start of the
! function. */
! static void
! rel_record_mem (addrp, addr, size, pre_offs, post_offs, insn, luid, call_tally)
! rtx *addrp, addr, insn;
! int size, pre_offs, post_offs;
! int luid, call_tally;
! {
! static rtx auto_inc;
! rtx orig_addr = *addrp;
! int regno, base;
! HOST_WIDE_INT offset;
! struct rel_use *new_use, *match;
! enum reg_class class;
! int hash;
!
! if (GET_CODE (addr) != REG)
! abort ();
!
! regno = REGNO (addr);
! if (! regno_related[regno] || ! regno_related[regno]->insn
! || regno_related[regno]->invalidate_luid)
! return;
!
! regno_related[regno]->reg_orig_refs += loop_depth;
!
! offset = regno_related[regno]->offset += pre_offs;
! base = regno_related[regno]->u.base;
!
! if (! auto_inc)
! {
! push_obstacks_nochange ();
! end_temporary_allocation ();
! auto_inc = gen_rtx_PRE_INC (Pmode, addr);
! pop_obstacks ();
! }
!
! XEXP (auto_inc, 0) = addr;
! *addrp = auto_inc;
!
! rel_new (new_use);
! new_use->insn = insn;
! new_use->addrp = addrp;
! new_use->luid = luid;
! new_use->call_tally = call_tally;
! new_use->class = class = reg_preferred_class (regno);
! new_use->set_in_parallel = 0;
! new_use->offset = offset;
! new_use->match_offset = offset;
! new_use->sibling = new_use;
!
! do
! {
! match = lookup_related (regno, class, offset);
! if (! match)
! {
! /* We can choose PRE_{IN,DE}CREMENT on the spot with the information
! we have gathered about the preceding instructions, while we have
! to record POST_{IN,DE}CREMENT possibilities so that we can check
! later if we have a use for their output value. */
! /* We use recog here directly because we are only testing here if
! the changes could be made, but don't really want to make a
! change right now. The caching from recog_memoized would only
! get in the way. */
! match = lookup_related (regno, class, offset - size);
! if (HAVE_PRE_INCREMENT && match)
! {
! PUT_CODE (auto_inc, PRE_INC);
! if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
! break;
! }
! match = lookup_related (regno, class, offset + size);
! if (HAVE_PRE_DECREMENT && match)
! {
! PUT_CODE (auto_inc, PRE_DEC);
! if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
! break;
! }
! match = 0;
! }
! PUT_CODE (auto_inc, POST_INC);
! if (HAVE_POST_INCREMENT && recog (PATTERN (insn), insn, NULL_PTR) >= 0)
! {
! struct rel_use *inc_use;
!
! rel_new (inc_use);
! *inc_use = *new_use;
! inc_use->sibling = new_use;
! new_use->sibling = inc_use;
! inc_use->prev_chain_ref = NULL_PTR;
! inc_use->next_chain = NULL_PTR;
! hash = REL_USE_HASH (inc_use->match_offset = offset + size);
! inc_use->next_hash = regno_related[base]->baseinfo->hashtab[hash];
! regno_related[base]->baseinfo->hashtab[hash] = inc_use;
! }
! PUT_CODE (auto_inc, POST_DEC);
! if (HAVE_POST_DECREMENT && recog (PATTERN (insn), insn, NULL_PTR) >= 0)
! {
! struct rel_use *dec_use;
!
! rel_new (dec_use);
! *dec_use = *new_use;
! dec_use->sibling = new_use->sibling;
! new_use->sibling = dec_use;
! dec_use->prev_chain_ref = NULL_PTR;
! dec_use->next_chain = NULL_PTR;
! hash = REL_USE_HASH (dec_use->match_offset = offset + size);
! dec_use->next_hash = regno_related[base]->baseinfo->hashtab[hash];
! regno_related[base]->baseinfo->hashtab[hash] = dec_use;
! }
! }
! while (0);
! rel_build_chain (new_use, match, base);
! *addrp = orig_addr;
!
! regno_related[regno]->offset += post_offs;
! }
!
! /* Note that REG is set to something that we do not regognize as a
! related value, at an insn with linear uid LUID. */
! static void
! invalidate_related (reg, luid, call_tally)
! rtx reg;
! int luid;
! {
! int regno = REGNO (reg);
! struct related *rel = regno_related[regno];
! if (! rel)
! {
! rel_new (rel);
! regno_related[regno] = rel;
! rel->prev = unrelatedly_used;
! unrelatedly_used = rel;
! rel->reg = reg;
! rel->insn = NULL_RTX;
! rel->invalidate_luid = 0;
! rel->u.last_luid = luid;
! }
! else if (rel->invalidate_luid)
! ; /* do nothing */
! else if (! rel->insn)
! rel->u.last_luid = luid;
! else
! {
! rel->invalidate_luid = luid;
! rel->reg_orig_calls_crossed = call_tally - rel->reg_set_call_tally;
! }
! }
!
! /* Check the RTL fragment pointed to by XP for related values - that is,
! if any new are created, or if they are assigned new values. Also
! note any other sets so that we can track lifetime conflicts.
! INSN is the instruction XP points into, LUID its luid, and CALL_TALLY
! the number of preceding calls in the function. */
! static void
! find_related (xp, insn, luid, call_tally)
! rtx *xp, insn;
! int luid, call_tally;
! {
! rtx x = *xp;
! enum rtx_code code = GET_CODE (x);
! const char *fmt;
! int i;
!
! switch (code)
! {
! case SET:
! {
! rtx dst = SET_DEST (x);
! rtx src = SET_SRC (x);
!
! /* First, check out if this sets a new related value.
! We don't care about register class differences here, since
! we might still find multiple related values share the same
! class even if it is disjunct from the class of the original
! register.
! We use a do .. while (0); here because there are many possible
! conditions that make us want to handle this like an ordinary set. */
! do
! {
! rtx src_reg, src_const;
! int src_regno, dst_regno;
! struct related *new_related;
!
! /* First check that we have actually something like
! (set (reg pseudo_dst) (plus (reg pseudo_src) (const_int))) . */
! if (GET_CODE (src) == PLUS)
! {
! src_reg = XEXP (src, 0);
! src_const = XEXP (src, 1);
! }
! else if (GET_CODE (src) == REG
! && GET_MODE_CLASS (GET_MODE (src)) == MODE_INT)
! {
! src_reg = src;
! src_const = const0_rtx;
! }
! else
! break;
!
! if (GET_CODE (src_reg) != REG
! || GET_CODE (src_const) != CONST_INT
! || GET_CODE (dst) != REG)
! break;
! dst_regno = REGNO (dst);
! src_regno = REGNO (src_reg);
!
! /* If only some words of multi-word pseudo are stored into, the
! old value does not die at the store, yet we can't replace the
! register. We cannot handle this case, so reject any pseudos
! that have such stores.
! We approximate this with REG_CHANGES_SIZE, which is true also
! in a few cases that we could handle (i.e. same number of words,
! or size change only when reading). */
! if (src_regno < FIRST_PSEUDO_REGISTER
! || REG_CHANGES_SIZE (src_regno)
! || dst_regno < FIRST_PSEUDO_REGISTER
! || REG_CHANGES_SIZE (dst_regno))
! break;
!
! /* We only know how to remove the set if that is
! all what the insn does. */
! if (x != single_set (insn))
! break;
!
! /* We cannot handle multiple lifetimes. */
! if ((regno_related[src_regno]
! && regno_related[src_regno]->invalidate_luid)
! || (regno_related[dst_regno]
! && regno_related[dst_regno]->invalidate_luid))
! break;
!
! /* Check if this is merely an update of a register with a
! value belonging to a group of related values we already
! track. */
! if (regno_related[dst_regno] && regno_related[dst_regno]->insn)
! {
! struct update *new_update;
!
! /* If the base register changes, don't handle this as a
! related value. We can currently only attribute the
! register to one base, and keep record of one lifetime
! during which we might re-use the register. */
! if (! regno_related[src_regno]
! || ! regno_related[src_regno]->insn
! ||(regno_related[dst_regno]->u.base
! != regno_related[src_regno]->u.base))
! break;
! regno_related[src_regno]->reg_orig_refs += loop_depth;
! regno_related[dst_regno]->reg_orig_refs += loop_depth;
! regno_related[dst_regno]->offset
! = regno_related[src_regno]->offset + INTVAL (src_const);
! rel_new (new_update);
! new_update->insn = insn;
! new_update->death_insn = regno_related[dst_regno]->death;
! regno_related[dst_regno]->death = NULL_RTX;
! new_update->prev = regno_related[dst_regno]->updates;
! regno_related[dst_regno]->updates = new_update;
! return;
! }
! if (! regno_related[src_regno]
! || ! regno_related[src_regno]->insn)
! {
! if (src_regno == dst_regno)
! break;
! rel_new (new_related);
! new_related->reg = src_reg;
! new_related->insn = insn;
! new_related->updates = 0;
! new_related->reg_set_call_tally = call_tally;
! new_related->reg_orig_refs = loop_depth;
! new_related->u.base = src_regno;
! new_related->offset = 0;
! new_related->prev = 0;
! new_related->invalidate_luid = 0;
! new_related->death = NULL_RTX;
! rel_new (new_related->baseinfo);
! bzero ((char *) new_related->baseinfo,
! sizeof *new_related->baseinfo);
! new_related->baseinfo->prev_base = rel_base_list;
! rel_base_list = new_related;
! new_related->baseinfo->insn_luid = luid;
! regno_related[src_regno] = new_related;
! }
! /* If the destination register has been used since we started
! tracking this group of related values, there would be tricky
! lifetime problems that we don't want to tackle right now. */
! else if (regno_related[dst_regno]
! && (regno_related[dst_regno]->u.last_luid
! >= regno_related[regno_related[src_regno]->u.base]->baseinfo->insn_luid))
! break;
! rel_new (new_related);
! new_related->reg = dst;
! new_related->insn = insn;
! new_related->updates = 0;
! new_related->reg_set_call_tally = call_tally;
! new_related->reg_orig_refs = loop_depth;
! new_related->u.base = regno_related[src_regno]->u.base;
! new_related->offset =
! regno_related[src_regno]->offset + INTVAL (src_const);
! new_related->invalidate_luid = 0;
! new_related->death = NULL_RTX;
! new_related->prev = regno_related[src_regno]->prev;
! regno_related[src_regno]->prev = new_related;
! regno_related[dst_regno] = new_related;
! return;
! }
! while (0);
!
! /* The SET has not been recognized as setting up a related value.
! If the destination is ultimately a register, we have to
! invalidate what we have memorized about any related value
! previously stored into it. */
! while (GET_CODE (dst) == SUBREG
! || GET_CODE (dst) == ZERO_EXTRACT
! || GET_CODE (dst) == SIGN_EXTRACT
! || GET_CODE (dst) == STRICT_LOW_PART)
! dst = XEXP (dst, 0);
! if (GET_CODE (dst) == REG)
! {
! find_related (&SET_SRC (x), insn, luid, call_tally);
! invalidate_related (dst, luid, call_tally);
! return;
! }
! find_related (&SET_SRC (x), insn, luid, call_tally);
! find_related (&SET_DEST (x), insn, luid,
! call_tally + (GET_CODE (insn) == CALL_INSN));
! return;
! }
! case CLOBBER:
! {
! rtx dst = XEXP (x, 0);
! while (GET_CODE (dst) == SUBREG
! || GET_CODE (dst) == ZERO_EXTRACT
! || GET_CODE (dst) == SIGN_EXTRACT
! || GET_CODE (dst) == STRICT_LOW_PART)
! dst = XEXP (dst, 0);
! if (GET_CODE (dst) == REG)
! {
! int regno = REGNO (dst);
! struct related *rel = regno_related[regno];
!
! /* If this clobbers a register that belongs to a set of related
! values, we have to check if the same register appears somewhere
! else in the insn : this is then likely to be a match_dup. */
!
! if (rel
! && rel->insn
! && ! rel->invalidate_luid
! && xp != &PATTERN (insn)
! && count_occurrences (PATTERN (insn), dst) > 1)
! {
! enum reg_class class = reg_preferred_class (regno);
! struct rel_use *new_use, *match;
! HOST_WIDE_INT offset = rel->offset;
!
! rel_new (new_use);
! new_use->insn = insn;
! new_use->addrp = &XEXP (x, 0);
! new_use->luid = luid;
! new_use->call_tally = call_tally;
! new_use->class = class;
! new_use->set_in_parallel = 1;
! new_use->sibling = new_use;
! do
! {
! new_use->match_offset = new_use->offset = offset;
! match = lookup_related (regno, class, offset);
! offset++;
! }
! while (! match || match->luid != luid);
! rel_build_chain (new_use, match, rel->u.base);
! /* Prevent other registers from using the same chain. */
! new_use->next_chain = new_use;
! }
! invalidate_related (dst, luid, call_tally);
! return;
! }
! break;
! }
! case REG:
! {
! int regno = REGNO (x);
! if (! regno_related[regno])
! {
! rel_new (regno_related[regno]);
! regno_related[regno]->prev = unrelatedly_used;
! unrelatedly_used = regno_related[regno];
! regno_related[regno]->reg = x;
! regno_related[regno]->insn = NULL_RTX;
! regno_related[regno]->u.last_luid = luid;
! }
! else if (! regno_related[regno]->insn)
! regno_related[regno]->u.last_luid = luid;
! else if (! regno_related[regno]->invalidate_luid)
! {
! struct rel_use *new_use, *match;
! HOST_WIDE_INT offset;
! int base;
! enum reg_class class;
!
! regno_related[regno]->reg_orig_refs += loop_depth;
!
! offset = regno_related[regno]->offset;
! base = regno_related[regno]->u.base;
!
! rel_new (new_use);
! new_use->insn = insn;
! new_use->addrp = xp;
! new_use->luid = luid;
! new_use->call_tally = call_tally;
! new_use->class = class = reg_preferred_class (regno);
! new_use->set_in_parallel = 0;
! new_use->offset = offset;
! new_use->match_offset = offset;
! new_use->sibling = new_use;
!
! match = lookup_related (regno, class, offset);
! rel_build_chain (new_use, match, base);
! }
! return;
! }
! case MEM:
! {
! int size = GET_MODE_SIZE (GET_MODE (x));
! rtx *addrp= &XEXP (x, 0), addr = *addrp;
!
! switch (GET_CODE (addr))
! {
! case REG:
! rel_record_mem (addrp, addr, size, 0, 0,
! insn, luid, call_tally);
! return;
! case PRE_INC:
! rel_record_mem (addrp, XEXP (addr, 0), size, size, 0,
! insn, luid, call_tally);
! return;
! case POST_INC:
! rel_record_mem (addrp, XEXP (addr, 0), size, 0, size,
! insn, luid, call_tally);
! return;
! case PRE_DEC:
! rel_record_mem (addrp, XEXP (addr, 0), size, -size, 0,
! insn, luid, call_tally);
! return;
! case POST_DEC:
! rel_record_mem (addrp, XEXP (addr, 0), size, 0, -size,
! insn, luid, call_tally);
! return;
! default:
! break;
! }
! break;
! }
! case PARALLEL:
! {
! for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
! {
! rtx *yp = &XVECEXP (x, 0, i);
! rtx y = *yp;
! if (GET_CODE (y) == SET)
! {
! rtx dst;
!
! find_related (&SET_SRC (y), insn, luid, call_tally);
! dst = SET_DEST (y);
! while (GET_CODE (dst) == SUBREG
! || GET_CODE (dst) == ZERO_EXTRACT
! || GET_CODE (dst) == SIGN_EXTRACT
! || GET_CODE (dst) == STRICT_LOW_PART)
! dst = XEXP (dst, 0);
! if (GET_CODE (dst) != REG)
! find_related (&SET_DEST (y), insn, luid,
! call_tally + (GET_CODE (insn) == CALL_INSN));
! }
! else if (GET_CODE (y) != CLOBBER)
! find_related (yp, insn, luid, call_tally);
! }
! for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
! {
! rtx *yp = &XVECEXP (x, 0, i);
! rtx y = *yp;
! if (GET_CODE (y) == SET)
! {
! rtx *dstp;
!
! dstp = &SET_DEST (y);
! while (GET_CODE (*dstp) == SUBREG
! || GET_CODE (*dstp) == ZERO_EXTRACT
! || GET_CODE (*dstp) == SIGN_EXTRACT
! || GET_CODE (*dstp) == STRICT_LOW_PART)
! dstp = &XEXP (*dstp, 0);
! if (GET_CODE (*dstp) == REG)
! {
! int regno = REGNO (*dstp);
! rtx src = SET_SRC (y);
! if (regno_related[regno] && regno_related[regno]->insn
! && GET_CODE (src) == PLUS
! && XEXP (src, 0) == *dstp
! && GET_CODE (XEXP (src, 1)) == CONST_INT)
! {
! struct rel_use *new_use, *match;
! enum reg_class class;
!
! regno_related[regno]->reg_orig_refs += loop_depth;
! rel_new (new_use);
! new_use->insn = insn;
! new_use->addrp = dstp;
! new_use->luid = luid;
! new_use->call_tally = call_tally;
! new_use->class = class = reg_preferred_class (regno);
! new_use->set_in_parallel = 1;
! new_use->offset = regno_related[regno]->offset;
! new_use->match_offset
! = regno_related[regno]->offset
! += INTVAL (XEXP (src, 1));
! new_use->sibling = new_use;
! match = lookup_related (regno, class, new_use->offset);
! rel_build_chain (new_use, match,
! regno_related[regno]->u.base);
! }
! else
! /* We assume here that a CALL_INSN won't set a pseudo
! at the same time as a MEM that contains the pseudo
! - if that were the case, we'd have to use an
! incremented CALL_TALLY value. */
! invalidate_related (*dstp, luid, call_tally);
! }
! }
! else if (GET_CODE (y) == CLOBBER)
! find_related (yp, insn, luid, call_tally);
! }
! return;
! }
! default:
! break;
! }
! fmt = GET_RTX_FORMAT (code);
!
! for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
! {
! if (fmt[i] == 'e')
! find_related (&XEXP (x, i), insn, luid, call_tally);
! if (fmt[i] == 'E')
! {
! register int j;
! for (j = 0; j < XVECLEN (x, i); j++)
! find_related (&XVECEXP (x, i, j), insn, luid, call_tally);
! }
! }
! }
!
! /* Comparison functions for qsort. */
! static int
! chain_starts_earlier (chain1, chain2)
! const PTR chain1;
! const PTR chain2;
! {
! int d = ((*(struct rel_use_chain **)chain2)->start_luid
! - (*(struct rel_use_chain **)chain1)->start_luid);
! if (! d)
! d = ((*(struct rel_use_chain **)chain2)->chain->offset
! - (*(struct rel_use_chain **)chain1)->chain->offset);
! if (! d)
! d = ((*(struct rel_use_chain **)chain2)->chain->set_in_parallel
! - (*(struct rel_use_chain **)chain1)->chain->set_in_parallel);
! /* If set_in_parallel is not set on both chain's first use, they must
! differ in start_luid or offset, since otherwise they would use the
! same chain.
! Thus the remaining problem is with set_in_parallel uses; for these, we
! know that *addrp is a register. Since the same register may not be set
! multiple times in the same insn, the registers must be different. */
!
! if (! d)
! d = (REGNO (*(*(struct rel_use_chain **)chain2)->chain->addrp)
! - REGNO (*(*(struct rel_use_chain **)chain1)->chain->addrp));
! return d;
! }
!
! static int
! chain_ends_later (chain1, chain2)
! const PTR chain1;
! const PTR chain2;
! {
! int d = ((*(struct rel_use_chain **)chain1)->end->no_link_pred
! - (*(struct rel_use_chain **)chain2)->end->no_link_pred);
! if (! d)
! d = ((*(struct rel_use_chain **)chain1)->end_luid
! - (*(struct rel_use_chain **)chain2)->end_luid);
! if (! d)
! d = ((*(struct rel_use_chain **)chain2)->chain->offset
! - (*(struct rel_use_chain **)chain1)->chain->offset);
! if (! d)
! d = ((*(struct rel_use_chain **)chain2)->chain->set_in_parallel
! - (*(struct rel_use_chain **)chain1)->chain->set_in_parallel);
! /* If set_in_parallel is not set on both chain's first use, they must
! differ in start_luid or offset, since otherwise they would use the
! same chain.
! Thus the remaining problem is with set_in_parallel uses; for these, we
! know that *addrp is a register. Since the same register may not be set
! multiple times in the same insn, the registers must be different. */
!
! if (! d)
! d = (REGNO (*(*(struct rel_use_chain **)chain2)->chain->addrp)
! - REGNO (*(*(struct rel_use_chain **)chain1)->chain->addrp));
! return d;
! }
!
! static void
! count_sets (x, pat, trash)
! rtx x, pat;
! void *trash ATTRIBUTE_UNUSED;
! {
! if (GET_CODE (x) == REG)
! REG_N_SETS (REGNO (x))++;
! }
!
! /* Perform the optimization for a single set of related values.
! INSERT_AFTER is an instruction after which we may emit instructions
! to initialize registers that remain live beyond the end of the group
! of instructions which have been examined. */
! static struct related *
! optimize_related_values_1 (rel_base, luid, call_tally, insert_after,
! regmove_dump_file)
! struct related *rel_base;
! int luid, call_tally;
! rtx insert_after;
! FILE *regmove_dump_file;
! {
! struct related_baseinfo *baseinfo = rel_base->baseinfo;
! struct related *rel;
! struct rel_use_chain *chain, *chain0, **chain_starttab, **chain_endtab;
! struct rel_use_chain **pred_chainp, *pred_chain, *last_init_chain;
! int num_regs, num_av_regs, num_chains, num_linked, max_end_luid, i;
! int max_start_luid;
! struct rel_use_chain *rel_base_reg_user;
! int mode;
! HOST_WIDE_INT rel_base_reg_user_offset = 0;
!
! /* For any registers that are still live, we have to arrange
! to have them set to their proper values.
! Also count with how many registers (not counting base) we are
! dealing with here. */
! for (num_regs = -1, rel = rel_base; rel; rel = rel->prev, num_regs++)
! {
! int regno = REGNO (rel->reg);
!
! if (! rel->death
! && ! rel->invalidate_luid)
! {
! enum reg_class class = reg_preferred_class (regno);
! struct rel_use *new_use, *match;
!
! rel_new (new_use);
! new_use->insn = NULL_RTX;
! new_use->addrp = &rel->reg;
! new_use->luid = luid;
! new_use->call_tally = call_tally;
! new_use->class = class;
! new_use->set_in_parallel = 1;
! new_use->match_offset = new_use->offset = rel->offset;
! new_use->sibling = new_use;
! match = lookup_related (regno, class, rel->offset);
! rel_build_chain (new_use, match, REGNO (rel_base->reg));
! /* Prevent other registers from using the same chain. */
! new_use->next_chain = new_use;
!
! rel->reg_orig_calls_crossed = call_tally - rel->reg_set_call_tally;
! }
! }
!
! /* Now for every chain of values related to the base, set start
! and end luid, match_offset, and reg. Also count the number of these
! chains, and determine the largest end luid. */
! num_chains = 0;
! for (max_end_luid = 0, chain = baseinfo->chains; chain; chain = chain->prev)
! {
! struct rel_use *use, *next;
!
! num_chains++;
! next = chain->chain;
! chain->start_luid = next->luid;
! do
! {
! use = next;
! next = use->next_chain;
! }
! while (next && next != use);
! use->no_link_pred = next != NULL_PTR;
! use->next_chain = 0;
! chain->end = use;
! chain->end_luid = use->luid;
! chain->match_offset = use->match_offset;
! chain->calls_crossed = use->call_tally - chain->chain->call_tally;
!
! chain->reg = use->insn ? NULL_RTX : *use->addrp;
!
! if (use->luid > max_end_luid)
! max_end_luid = use->luid;
!
! if (regmove_dump_file)
! fprintf (regmove_dump_file, "Chain start: %d end: %d\n",
! chain->start_luid, chain->end_luid);
! }
!
! if (regmove_dump_file)
! fprintf (regmove_dump_file,
! "Insn %d reg %d: found %d chains.\n",
! INSN_UID (rel_base->insn), REGNO (rel_base->reg), num_chains);
!
! if (! num_chains)
! return baseinfo->prev_base;
!
! /* For every chain, we try to find another chain the lifetime of which
! ends before the lifetime of said chain starts.
! So we first sort according to luid of first and last instruction that
! is in the chain, respectively; this is O(n * log n) on average. */
! chain_starttab = rel_alloc (num_chains * sizeof *chain_starttab);
! chain_endtab = rel_alloc (num_chains * sizeof *chain_starttab);
! for (chain = baseinfo->chains, i = 0; chain; chain = chain->prev, i++)
! {
! chain_starttab[i] = chain;
! chain_endtab[i] = chain;
! }
! qsort (chain_starttab, num_chains, sizeof *chain_starttab,
! chain_starts_earlier);
! qsort (chain_endtab, num_chains, sizeof *chain_endtab, chain_ends_later);
!
!
! /* Now we go through every chain, starting with the one that starts
! second (we can skip the first because we know there would be no match),
! and check it against the chain that ends first. */
! /* ??? We assume here that reg_class_compatible_p will seldom return false.
! If that is not true, we should do a more thorough search for suitable
! chain combinations. */
! pred_chainp = chain_endtab;
! pred_chain = *pred_chainp;
! max_start_luid = chain_starttab[num_chains - 1]->start_luid;
! for (num_linked = 0, i = num_chains - 2; i >= 0; i--)
! {
! struct rel_use_chain *succ_chain = chain_starttab[i];
! if (succ_chain->start_luid > pred_chain->end_luid
! && ! pred_chain->end->no_link_pred
! && (pred_chain->calls_crossed
! ? succ_chain->calls_crossed
! : succ_chain->end->call_tally == pred_chain->chain->call_tally)
! && regclass_compatible_p (succ_chain->chain->class,
! pred_chain->chain->class)
! /* add_limits is not valid for MODE_PARTIAL_INT . */
! && GET_MODE_CLASS (GET_MODE (rel_base->reg)) == MODE_INT
! && (succ_chain->chain->offset - pred_chain->match_offset
! >= add_limits[(int) GET_MODE (rel_base->reg)][0])
! && (succ_chain->chain->offset - pred_chain->match_offset
! <= add_limits[(int) GET_MODE (rel_base->reg)][1]))
! {
! /* We can link these chains together. */
! pred_chain->linked = succ_chain;
! succ_chain->start_luid = 0;
! num_linked++;
!
! pred_chain = *++pred_chainp;
! }
! else
! max_start_luid = succ_chain->start_luid;
! }
!
! if (regmove_dump_file && num_linked)
! fprintf (regmove_dump_file, "Linked to %d sets of chains.\n",
! num_chains - num_linked);
!
! /* Now count the number of registers that are available for reuse. */
! /* ??? In rare cases, we might reuse more if we took different
! end luids of the chains into account. Or we could just allocate
! some new regs. But that would probably not be worth the effort. */
! /* ??? We should pay attention to preferred register classes here to,
! if the to-be-allocated register have a life outside the range that
! we handle. */
! for (num_av_regs = 0, rel = rel_base->prev; rel; rel = rel->prev)
! {
! if (! rel->invalidate_luid
! || rel->invalidate_luid > max_end_luid)
! num_av_regs++;
! }
!
! /* Propagate mandatory register assignments to the first chain in
! all sets of liked chains, and set rel_base_reg_user. */
! for (rel_base_reg_user = 0, i = 0; i < num_chains; i++)
! {
! struct rel_use_chain *chain = chain_starttab[i];
! if (chain->linked)
! chain->reg = chain->linked->reg;
! if (chain->reg == rel_base->reg)
! rel_base_reg_user = chain;
! }
! /* If rel_base->reg is not a mandatory allocated register, allocate
! it to that chain that starts first and has no allocated register,
! and that allows the addition of the start value in a single
! instruction. */
! mode = (int) GET_MODE (rel_base->reg);
! if (! rel_base_reg_user)
! {
! for ( i = num_chains - 1; i >= 0; --i)
! {
! struct rel_use_chain *chain = chain_starttab[i];
! if (! chain->reg
! && chain->start_luid
! && chain->chain->offset >= add_limits[mode][0]
! && chain->chain->offset <= add_limits[mode][1]
! /* Also can't use this chain if it's register is clobbered
! and other chains need to start later. */
! && (! (chain->end->no_link_pred && chain->end->insn)
! || chain->end->luid >= max_start_luid)
! /* Also can't use it if it lasts longer than base
! base is available. */
! && (! rel_base->invalidate_luid
! || rel_base->invalidate_luid > chain->end_luid))
! {
! chain->reg = rel_base->reg;
! rel_base_reg_user = chain;
! break;
! }
! }
! }
! else
! rel_base_reg_user_offset = rel_base_reg_user->chain->offset;
!
! /* Now check if it is worth doing this optimization after all.
! Using separate registers per value, like in the code generated by cse,
! costs two instructions per register (one move and one add).
! Using the chains we have set up, we need two instructions for every
! linked set of chains, plus one instruction for every link;
! however, if the base register is allocated to a chain
! (i.e. rel_base_reg_user != 0), we don't need a move insn to start
! that chain.
! We do the optimization if we save instructions, or if we
! stay with the same number of instructions, but save registers.
! We also require that we have enough registers available for reuse.
! Moreover, we have to check that we can add the offset for
! rel_base_reg_user, in case it is a mandatory allocated register. */
! if ((2 * num_regs
! > ((2 * num_chains - num_linked - (rel_base_reg_user != 0))
! - (num_linked != 0)))
! && num_av_regs + (rel_base_reg_user != 0) >= num_chains - num_linked
! && rel_base_reg_user_offset >= add_limits[mode][0]
! && rel_base_reg_user_offset <= add_limits[mode][1])
! {
! /* Hold the current offset between the initial value of rel_base->reg
! and the current value of rel_base->rel before the instruction
! that starts the current set of chains. */
! int base_offset = 0;
! /* The next use of rel_base->reg that we have to look out for. */
! struct rel_use *base_use;
! /* Pointer to next insn where we look for it. */
! rtx base_use_scan = 0;
! int base_last_use_call_tally = rel_base->reg_set_call_tally;
! int base_regno;
! int base_seen;
!
! if (regmove_dump_file)
! fprintf (regmove_dump_file, "Optimization is worth while.\n");
!
! /* First, remove all the setting insns, death notes
! and refcount increments that are now obsolete. */
! for (rel = rel_base; rel; rel = rel->prev)
! {
! struct update *update;
! int regno = REGNO (rel->reg);
!
! if (rel != rel_base)
! {
! /* The first setting insn might be the start of a basic block. */
! if (rel->insn == rel_base->insn
! /* We have to preserve insert_after. */
! || rel->insn == insert_after)
! {
! PUT_CODE (rel->insn, NOTE);
! NOTE_LINE_NUMBER (rel->insn) = NOTE_INSN_DELETED;
! NOTE_SOURCE_FILE (rel->insn) = 0;
! }
! else
! delete_insn (rel->insn);
! REG_N_SETS (regno)--;
! }
! REG_N_CALLS_CROSSED (regno) -= rel->reg_orig_calls_crossed;
! for (update = rel->updates; update; update = update->prev)
! {
! rtx death_insn = update->death_insn;
! if (death_insn)
! {
! rtx death_note
! = find_reg_note (death_insn, REG_DEAD, rel->reg);
! if (! death_note)
! death_note
! = find_reg_note (death_insn, REG_UNUSED, rel->reg);
! remove_note (death_insn, death_note);
! REG_N_DEATHS (regno)--;
! }
! /* We have to preserve insert_after. */
! if (update->insn == insert_after)
! {
! PUT_CODE (update->insn, NOTE);
! NOTE_LINE_NUMBER (update->insn) = NOTE_INSN_DELETED;
! NOTE_SOURCE_FILE (update->insn) = 0;
! }
! else
! delete_insn (update->insn);
! REG_N_SETS (regno)--;
! }
! if (rel->death)
! {
! rtx death_note = find_reg_note (rel->death, REG_DEAD, rel->reg);
! if (! death_note)
! death_note = find_reg_note (rel->death, REG_UNUSED, rel->reg);
! remove_note (rel->death, death_note);
! rel->death = death_note;
! REG_N_DEATHS (regno)--;
! }
! }
! /* Go through all the chains and install the planned changes. */
! rel = rel_base;
! if (rel_base_reg_user)
! {
! base_use = rel_base_reg_user->chain;
! base_use_scan = chain_starttab[num_chains - 1]->chain->insn;
! }
!
! /* Set last_init_chain to the chain that starts latest. */
! for (i = 0; ! chain_starttab[i]->start_luid; i++);
! last_init_chain = chain_starttab[i];
! /* If there are multiple chains that consist only of an
! assignment to a register that is live at the end of the
! block, they all have the same luid. The loop that emits the
! insns for all the chains below starts with the chain with the
! highest index, and due to the way insns are emitted after
! insert_after, the first emitted will eventually be the last. */
! for (; i < num_chains; i++)
! {
! if (! chain_starttab[i]->start_luid)
! continue;
! if (chain_starttab[i]->chain->insn)
! break;
! last_init_chain = chain_starttab[i];
! }
!
! base_regno = REGNO (rel_base->reg);
! base_seen = 0;
! for (i = num_chains - 1; i >= 0; i--)
! {
! int first_call_tally;
! rtx reg;
! int regno;
! struct rel_use *use, *last_use;
!
! chain0 = chain_starttab[i];
! if (! chain0->start_luid)
! continue;
! first_call_tally = chain0->chain->call_tally;
! reg = chain0->reg;
! /* If this chain has not got a register yet, assign one. */
! if (! reg)
! {
! do
! rel = rel->prev;
! while (! rel->death
! || (rel->invalidate_luid
! && rel->invalidate_luid <= max_end_luid));
! reg = rel->reg;
! }
! regno = REGNO (reg);
!
! use = chain0->chain;
!
! /* Update base_offset. */
! if (rel_base_reg_user)
! {
! rtx use_insn = use->insn;
! rtx base_use_insn = base_use->insn;
!
! if (! use_insn)
! use_insn = insert_after;
!
! while (base_use_scan != use_insn)
! {
! if (base_use_scan == base_use_insn)
! {
! base_offset = base_use->match_offset;
! base_use = base_use->next_chain;
! if (! base_use)
! {
! rel_base_reg_user = rel_base_reg_user->linked;
! if (! rel_base_reg_user)
! break;
! base_use = rel_base_reg_user->chain;
! }
! base_use_insn = base_use->insn;
! }
! base_use_scan = NEXT_INSN (base_use_scan);
! }
! /* If we are processing the start of a chain that starts with
! an instruction that also uses the base register, (that happens
! only if USE_INSN contains multiple distinct, but related
! values) and the chains using the base register have already
! been processed, the initializing instruction of the new
! register will end up after the adjustment of the base
! register. */
! if (use_insn == base_use_insn && base_seen)
! base_offset = base_use->offset;
! }
! if (regno == base_regno)
! base_seen = 1;
! if (regno != base_regno || use->offset - base_offset)
! {
! HOST_WIDE_INT offset = use->offset - base_offset;
! rtx add;
!
! add = (offset
! ? gen_add3_insn (reg, rel_base->reg, GEN_INT (offset))
! : gen_move_insn (reg, rel_base->reg));
! if (! add)
! abort ();
! if (GET_CODE (add) == SEQUENCE)
! {
! int i;
!
! for (i = XVECLEN (add, 0) - 1; i >= 0; i--)
! note_stores (PATTERN (XVECEXP (add, 0, i)), count_sets,
! NULL);
! }
! else
! note_stores (add, count_sets, NULL);
! if (use->insn)
! add = emit_insn_before (add, use->insn);
! else
! add = emit_insn_after (add, insert_after);
! if (use->call_tally > base_last_use_call_tally)
! base_last_use_call_tally = use->call_tally;
! /* If this is the last reg initializing insn, and we
! still have to place a death note for the base reg,
! attach it to this insn -
! unless we are still using the base register. */
! if (chain0 == last_init_chain
! && rel_base->death
! && regno != base_regno)
! {
! XEXP (rel_base->death, 0) = rel_base->reg;
! XEXP (rel_base->death, 1) = REG_NOTES (add);
! REG_NOTES (add) = rel_base->death;
! REG_N_DEATHS (base_regno)++;
! }
! }
! for (last_use = 0, chain = chain0; chain; chain = chain->linked)
! {
! int last_offset;
!
! use = chain->chain;
! if (last_use && use->offset != last_use->offset)
! {
! rtx add
! = gen_add3_insn (reg, reg,
! GEN_INT (use->offset - last_use->offset));
! if (! add)
! abort ();
! if (use->insn)
! emit_insn_before (add, use->insn);
! else
! {
! /* Set use->insn, so that base_offset will be adjusted
! in time if REG is REL_BASE->REG . */
! use->insn = emit_insn_after (add, last_use->insn);
! }
! REG_N_SETS (regno)++;
! }
! for (last_offset = use->offset; use; use = use->next_chain)
! {
! rtx addr;
! int use_offset;
!
! addr = *use->addrp;
! if (GET_CODE (addr) != REG)
! remove_note (use->insn,
! find_reg_note (use->insn, REG_INC,
! XEXP (addr, 0)));
! use_offset = use->offset;
! if (use_offset == last_offset)
! {
! if (use->set_in_parallel)
! {
! REG_N_SETS (REGNO (addr))--;
! addr = reg;
! }
! else if (use->match_offset > use_offset)
! addr = gen_rtx_POST_INC (Pmode, reg);
! else if (use->match_offset < use_offset)
! addr = gen_rtx_POST_DEC (Pmode, reg);
! else
! addr = reg;
! }
! else if (use_offset > last_offset)
! addr = gen_rtx_PRE_INC (Pmode, reg);
! else
! addr = gen_rtx_PRE_DEC (Pmode, reg);
! /* Group changes from the same chain for the same insn
! together, to avoid failures for match_dups. */
! validate_change (use->insn, use->addrp, addr, 1);
! if ((! use->next_chain || use->next_chain->insn != use->insn)
! && ! apply_change_group ())
! abort ();
! if (addr != reg)
! REG_NOTES (use->insn)
! = gen_rtx_EXPR_LIST (REG_INC, reg, REG_NOTES (use->insn));
! last_use = use;
! last_offset = use->match_offset;
! }
! }
! /* If REG dies, attach its death note to the last using insn in
! the set of linked chains we just handled.
! However, if REG is the base register, don't do this if there
! will be a later initializing instruction for another register.
! The initializing instruction for last_init_chain will be inserted
! before last_init_chain->chain->insn, so if the luids (and hence
! the insns these stand for) are equal, put the death note here. */
! if (reg == rel->reg
! && rel->death
! && (rel != rel_base
! || last_use->luid >= last_init_chain->start_luid))
! {
! XEXP (rel->death, 0) = reg;
!
! /* Note that passing only PATTERN (LAST_USE->insn) to
! reg_set_p here is not enough, since we might have
! created an REG_INC for REG above. */
!
! PUT_MODE (rel->death, (reg_set_p (reg, last_use->insn)
! ? REG_UNUSED : REG_DEAD));
! XEXP (rel->death, 1) = REG_NOTES (last_use->insn);
! REG_NOTES (last_use->insn) = rel->death;
! /* Mark this death as 'used up'. That is important for the
! base register. */
! rel->death = NULL_RTX;
! REG_N_DEATHS (regno)++;
! }
! if (regno == base_regno)
! base_last_use_call_tally = last_use->call_tally;
! else
! REG_N_CALLS_CROSSED (regno)
! += last_use->call_tally - first_call_tally;
! }
!
! REG_N_CALLS_CROSSED (base_regno) +=
! base_last_use_call_tally - rel_base->reg_set_call_tally;
! }
!
! /* Finally, clear the entries that we used in regno_related. We do it
! item by item here, because doing it with bzero for each basic block
! would give O(n*n) time complexity. */
! for (rel = rel_base; rel; rel = rel->prev)
! regno_related[REGNO (rel->reg)] = 0;
! return baseinfo->prev_base;
! }
!
! /* Finalize the optimization for any related values know so far, and reset
! the entries in regno_related that we have disturbed. */
! static void
! optimize_related_values_0 (rel_base_list, luid, call_tally, insert_after,
! regmove_dump_file)
! struct related *rel_base_list;
! int luid, call_tally;
! rtx insert_after;
! FILE *regmove_dump_file;
! {
! while (rel_base_list)
! rel_base_list
! = optimize_related_values_1 (rel_base_list, luid, call_tally,
! insert_after, regmove_dump_file);
! for ( ; unrelatedly_used; unrelatedly_used = unrelatedly_used->prev)
! regno_related[REGNO (unrelatedly_used->reg)] = 0;
! }
!
! /* Scan the entire function for instances where multiple registers are
! set to values that differ only by a constant.
! Then try to reduce the number of instructions and/or registers needed
! by exploiting auto_increment and true two-address additions. */
!
! static void
! optimize_related_values (nregs, regmove_dump_file)
! int nregs;
! FILE *regmove_dump_file;
! {
! int b;
! rtx insn;
! int luid = 0;
! int call_tally = 0;
! int save_loop_depth = loop_depth;
! enum machine_mode mode;
!
! if (regmove_dump_file)
! fprintf (regmove_dump_file, "Starting optimize_related_values.\n");
!
! /* For each integer mode, find minimum and maximum value for a single-
! instruction reg-constant add. */
! for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
! mode = GET_MODE_WIDER_MODE (mode))
! {
! rtx reg = gen_rtx_REG (mode, FIRST_PSEUDO_REGISTER);
! int icode = (int) add_optab->handlers[(int) mode].insn_code;
! HOST_WIDE_INT tmp;
! rtx add, set;
! int p, p_max;
!
! add_limits[(int) mode][0] = 0;
! add_limits[(int) mode][1] = 0;
! if (icode == CODE_FOR_nothing
! || ! (*insn_data[icode].operand[0].predicate) (reg, mode)
! || ! (*insn_data[icode].operand[1].predicate) (reg, mode)
! || ! (*insn_data[icode].operand[2].predicate) (const1_rtx, mode))
! continue;
! add = GEN_FCN (icode) (reg, reg, const1_rtx);
! if (GET_CODE (add) == SEQUENCE)
! continue;
! add = make_insn_raw (add);
! set = single_set (add);
! if (! set
! || GET_CODE (SET_SRC (set)) != PLUS
! || XEXP (SET_SRC (set), 1) != const1_rtx)
! continue;
! p_max = GET_MODE_BITSIZE (mode) - 1;
! if (p_max > HOST_BITS_PER_WIDE_INT - 2)
! p_max = HOST_BITS_PER_WIDE_INT - 2;
! for (p = 2; p < p_max; p++)
! {
! if (! validate_change (add, &XEXP (SET_SRC (set), 1),
! GEN_INT (((HOST_WIDE_INT) 1 << p) - 1), 0))
! break;
! }
! add_limits[(int) mode][1] = tmp = INTVAL (XEXP (SET_SRC (set), 1));
! /* We need a range of known good values for the constant of the add.
! Thus, before checking for the power of two, check for one less first,
! in case the power of two is an exceptional value. */
! if (validate_change (add, &XEXP (SET_SRC (set), 1), GEN_INT (-tmp), 0))
! {
! if (validate_change (add, &XEXP (SET_SRC (set), 1),
! GEN_INT (-tmp - 1), 0))
! add_limits[(int) mode][0] = -tmp - 1;
! else
! add_limits[(int) mode][0] = -tmp;
! }
! }
!
! /* Insert notes before basic block ends, so that we can safely
! insert other insns.
! Don't do this when it would separate a BARRIER from the insn that
! it belongs to; we really need the notes only when the basic block
! end is due to a following label or to the end of the function.
! We must never dispose a JUMP_INSN as last insn of a basic block,
! since this confuses save_call_clobbered_regs. */
! for (b = 0; b < n_basic_blocks; b++)
! {
! rtx end = BLOCK_END (b);
! if (GET_CODE (end) != JUMP_INSN)
! {
! rtx next = next_nonnote_insn (BLOCK_END (b));
! if (! next || GET_CODE (next) != BARRIER)
! BLOCK_END (b) = emit_note_after (NOTE_INSN_DELETED, BLOCK_END (b));
! }
! }
!
! gcc_obstack_init (&related_obstack);
! regno_related = rel_alloc (nregs * sizeof *regno_related);
! bzero ((char *) regno_related, nregs * sizeof *regno_related);
! rel_base_list = 0;
! loop_depth = 1;
! b = -1;
!
! for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
! {
! luid++;
!
! /* Check to see if this is the first insn of the next block. There is
! no next block if we are already in the last block. */
! if ((b+1) < n_basic_blocks && insn == BLOCK_HEAD (b+1))
! b = b+1;
!
! if (GET_CODE (insn) == NOTE)
! {
! if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
! loop_depth++;
! else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
! loop_depth--;
! }
!
! /* Don't do anything before the start of the first basic block. */
! if (b < 0)
! continue;
!
! /* Don't do anything if this instruction is in the shadow of a
! live flags register. */
! if (GET_MODE (insn) == HImode)
! continue;
!
! if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
! {
! rtx note;
! find_related (&PATTERN (insn), insn, luid, call_tally);
! for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
! {
! if (REG_NOTE_KIND (note) == REG_DEAD
! || (REG_NOTE_KIND (note) == REG_UNUSED
! && GET_CODE (XEXP (note, 0)) == REG))
! {
! rtx reg = XEXP (note, 0);
! int regno = REGNO (reg);
! if (REG_NOTE_KIND (note) == REG_DEAD
! && reg_set_p (reg, PATTERN (insn)))
! {
! remove_note (insn, note);
! REG_N_DEATHS (regno)--;
! }
! else if (regno_related[regno]
! && ! regno_related[regno]->invalidate_luid)
! {
! regno_related[regno]->death = insn;
! regno_related[regno]->reg_orig_calls_crossed
! = call_tally - regno_related[regno]->reg_set_call_tally;
! }
! }
! }
! /* Inputs to a call insn do not cross the call, therefore CALL_TALLY
! must be bumped *after* they have been processed. */
! if (GET_CODE (insn) == CALL_INSN)
! call_tally++;
! }
!
! /* We end current processing at the end of a basic block, or when
! a flags register becomes live.
!
! Otherwise, we might end up with one or more extra instructions
! inserted in front of the user, to set up or adjust a register.
! There are cases where this could be handled smarter, but most of
! the time the user will be a branch anyways, so the extra effort
! to handle the occasional conditional instruction is probably not
! justified by the little possible extra gain. */
!
! if (insn == BLOCK_END (b)
! || GET_MODE (insn) == QImode)
! {
! optimize_related_values_0 (rel_base_list, luid, call_tally,
! prev_nonnote_insn (insn),
! regmove_dump_file);
! rel_base_list = 0;
! }
! }
! optimize_related_values_0 (rel_base_list, luid, call_tally,
! get_last_insn (), regmove_dump_file);
! obstack_free (&related_obstack, 0);
! loop_depth = save_loop_depth;
! if (regmove_dump_file)
! fprintf (regmove_dump_file, "Finished optimize_related_values.\n");
! }
!
! #endif /* AUTO_INC_DEC */
!
static int *regno_src_regno;
/* Indicate how good a choice REG (which appears as a source) is to replace
*************** copy_src_to_dest (insn, src, dest, loop_
*** 796,801 ****
--- 2449,2455 ----
seq = gen_sequence ();
end_sequence ();
/* If this sequence uses new registers, we may not use it. */
+ /* ????? This code no longer works since no_new_pseudos is set. */
if (old_num_regs != reg_rtx_no
|| ! validate_replace_rtx (src, dest, insn))
{
*************** regmove_optimize (f, nregs, regmove_dump
*** 1098,1103 ****
--- 2752,2763 ----
/* Find out where a potential flags register is live, and so that we
can supress some optimizations in those zones. */
mark_flags_life_zones (discover_flags_reg ());
+ #ifdef AUTO_INC_DEC
+ /* See the comment in front of REL_USE_HASH_SIZE what
+ this is about. */
+ if (flag_regmove && flag_expensive_optimizations)
+ optimize_related_values (nregs, regmove_dump_file);
+ #endif
regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
*************** regmove_optimize (f, nregs, regmove_dump
*** 1196,1206 ****
src = recog_data.operand[op_no];
dst = recog_data.operand[match_no];
- if (GET_CODE (src) != REG)
- continue;
-
src_subreg = src;
if (GET_CODE (dst) == SUBREG
&& GET_MODE_SIZE (GET_MODE (dst))
>= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
{
--- 2856,2864 ----
src = recog_data.operand[op_no];
dst = recog_data.operand[match_no];
src_subreg = src;
if (GET_CODE (dst) == SUBREG
+ && GET_CODE (src) == REG
&& GET_MODE_SIZE (GET_MODE (dst))
>= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
{
*************** regmove_optimize (f, nregs, regmove_dump
*** 1209,1215 ****
src, SUBREG_WORD (dst));
dst = SUBREG_REG (dst);
}
! if (GET_CODE (dst) != REG
|| REGNO (dst) < FIRST_PSEUDO_REGISTER)
continue;
--- 2867,2879 ----
src, SUBREG_WORD (dst));
dst = SUBREG_REG (dst);
}
! else if (GET_CODE (src) == SUBREG
! && (GET_MODE_SIZE (GET_MODE (src))
! >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
! src = SUBREG_REG (src);
!
! if (GET_CODE (src) != REG
! || GET_CODE (dst) != REG
|| REGNO (dst) < FIRST_PSEUDO_REGISTER)
continue;
*************** fixup_match_1 (insn, set, src, src_subre
*** 1871,1876 ****
--- 3535,3553 ----
validate_change (insn, recog_data.operand_loc[match_number], src, 1);
if (validate_replace_rtx (dst, src_subreg, p))
success = 1;
+ else if (src_subreg != src
+ && *recog_data.operand_loc[match_number] == dst)
+ {
+ /* In this case, we originally have a subreg in the src
+ operand. It's mode should match the destination operand.
+ Moreover, P is likely to use DST in a subreg, so replacing
+ it with another subreg will fail - but putting the raw
+ register there can succeed. */
+ validate_change (insn, recog_data.operand_loc[match_number],
+ src_subreg, 1);
+ if (validate_replace_rtx (dst, src, p))
+ success = 1;
+ }
break;
}
More information about the Gcc-patches
mailing list