change-stack rewrite
Jan Hubicka
hubicka@atrey.karlin.mff.cuni.cz
Sat Oct 30 16:11:00 GMT 1999
Hi
This patch rewrites change_stack to not emit unnecesary insns.
It also emits more "pop top of stack" insns that may in future
result in more ffreep instructions on Athlon and more "double pop"
fcompp instructions.
I've split real functionality to change_to_regmap, that allows more
flexibility - you may specify the permutation just partially.
This is usefull for example when outputing the asm statements.
I also have more use for such relocation maps in my other code.
Fri Sep 30 17:37:04 CEST 1999 Jan Hubicka <hubicka@freesoft.cz>
* reg-stack.c (change_stack): Rewrite to call change_to_regmap.
(change_to_regmap): New.
(subst_asm_stack_regs): Use change_to_regmap instead of
change_stack.
*** reg-stack.c.old Fri Oct 29 08:21:23 1999
--- reg-stack.c Sat Oct 30 17:35:06 1999
*************** static void compare_for_stack_reg PROTO(
*** 251,257 ****
static void subst_stack_regs_pat PROTO((rtx, stack, rtx));
static void subst_asm_stack_regs PROTO((rtx, stack));
static void subst_stack_regs PROTO((rtx, stack));
! static void change_stack PROTO((rtx, stack, stack,
enum emit_where));
static int convert_regs_entry PROTO((void));
static void convert_regs_exit PROTO((void));
--- 251,259 ----
static void subst_stack_regs_pat PROTO((rtx, stack, rtx));
static void subst_asm_stack_regs PROTO((rtx, stack));
static void subst_stack_regs PROTO((rtx, stack));
! static int change_stack PROTO((rtx, stack, stack,
! enum emit_where));
! static int change_to_regmap PROTO((rtx, stack, int *,
enum emit_where));
static int convert_regs_entry PROTO((void));
static void convert_regs_exit PROTO((void));
*************** subst_asm_stack_regs (insn, regstack)
*** 1772,1783 ****
rtx *clobber_reg;
rtx **clobber_loc;
- struct stack_def temp_stack;
int n_notes;
int n_clobbers;
rtx note;
int i;
int n_inputs, n_outputs;
if (! check_asm_stack_operands (insn))
return;
--- 1774,1785 ----
rtx *clobber_reg;
rtx **clobber_loc;
int n_notes;
int n_clobbers;
rtx note;
int i;
int n_inputs, n_outputs;
+ int regmap [LAST_STACK_REG+1];
if (! check_asm_stack_operands (insn))
return;
*************** subst_asm_stack_regs (insn, regstack)
*** 1869,1875 ****
}
}
! temp_stack = *regstack;
/* Put the input regs into the desired place in TEMP_STACK. */
--- 1871,1878 ----
}
}
! for (i = FIRST_STACK_REG; i <= LAST_STACK_REG ; i++)
! regmap [i] = -2;
/* Put the input regs into the desired place in TEMP_STACK. */
*************** subst_asm_stack_regs (insn, regstack)
*** 1886,1918 ****
we can just use REGNO (recog_data.operand[i]) to know which
actual reg this operand needs to be in. */
! int regno = get_hard_regnum (&temp_stack, recog_data.operand[i]);
!
! if (regno < 0)
! abort ();
- if (regno != REGNO (recog_data.operand[i]))
- {
- /* recog_data.operand[i] is not in the right place. Find
- it and swap it with whatever is already in I's place.
- K is where recog_data.operand[i] is now. J is where it
- should be. */
- int j, k, temp;
-
- k = temp_stack.top - (regno - FIRST_STACK_REG);
- j = (temp_stack.top
- - (REGNO (recog_data.operand[i]) - FIRST_STACK_REG));
-
- temp = temp_stack.reg[k];
- temp_stack.reg[k] = temp_stack.reg[j];
- temp_stack.reg[j] = temp;
- }
}
/* Emit insns before INSN to make sure the reg-stack is in the right
order. */
! change_stack (insn, regstack, &temp_stack, EMIT_BEFORE);
/* Make the needed input register substitutions. Do death notes and
clobbers too, because these are for inputs, not outputs. */
--- 1889,1903 ----
we can just use REGNO (recog_data.operand[i]) to know which
actual reg this operand needs to be in. */
! regmap [REGNO (recog_data.operand[i])]
! = regstack -> top + FIRST_STACK_REG - REGNO (recog_data.operand[i]);
}
/* Emit insns before INSN to make sure the reg-stack is in the right
order. */
! change_to_regmap (insn, regstack, regmap, EMIT_BEFORE);
/* Make the needed input register substitutions. Do death notes and
clobbers too, because these are for inputs, not outputs. */
*************** subst_stack_regs (insn, regstack)
*** 2128,2155 ****
note_link = &XEXP (note, 1);
}
! /* Change the organization of the stack so that it fits a new basic
! block. Some registers might have to be popped, but there can never be
! a register live in the new block that is not now live.
Insert any needed insns before or after INSN, as indicated by
WHERE. OLD is the original stack layout, and NEW is the desired
form. OLD is updated to reflect the code emitted, ie, it will be
the same as NEW upon return.
! This function will not preserve block_end[]. But that information
! is no longer needed once this has executed. */
!
! static void
! change_stack (insn, old, new, where)
rtx insn;
stack old;
! stack new;
enum emit_where where;
{
- int reg;
int update_end = 0;
!
/* We will be inserting new insns "backwards". If we are to insert
after INSN, find the next insn, and insert before it. */
--- 2113,2190 ----
note_link = &XEXP (note, 1);
}
! /* Find cycle in partial permutation.
! Helper function for change_to_regmap. */
! static int
! find_cycle (registermap, s)
! int *registermap;
! stack s;
! {
! int i;
! for (i = 0; i <= s->top; i++)
! {
! int y;
! int pos = registermap[(int) s->reg[i]];
! y = pos;
! if (y >= 0 && y != i)
! {
! do
! y = registermap[(int) s->reg[y]];
! while (y != pos && y >= 0);
!
! if (y >= 0)
! return i;
! }
! }
! return -1;
! }
!
! /* Find beggining of path in partial permutation.
! Helper function for change_to_regmap. */
! static int
! find_path (registermap, s)
! int *registermap;
! stack s;
! {
! int i;
! for (i = 0; i <= s->top; i++)
! {
! int pos = registermap[(int) s->reg[i]];
! if (pos >= 0 && pos != i)
! {
! int z;
! for (z = 0; z <= s->top; z++)
! if (registermap[(int) s->reg[z]] == i)
! break;
! if (z > s->top)
! return i;
! }
! }
! return -1;
! }
!
! /* Emit code to change stack according to the REGMAP. Regmap is array,
! where for each hardreg in the range FIRST_STACK_REG to LAST_STACK_REG
! is stored it's required possition in new stack, -1 when it needs to be
! popped and -2 if it may appear anywhere.
Insert any needed insns before or after INSN, as indicated by
WHERE. OLD is the original stack layout, and NEW is the desired
form. OLD is updated to reflect the code emitted, ie, it will be
the same as NEW upon return.
! When final is nonzero, change_stack is not allowed to modify basic block
! interface.
! */
! static int
! change_to_regmap (insn, old, regmap, where)
rtx insn;
stack old;
! int *regmap;
enum emit_where where;
{
int update_end = 0;
! int ninsns = 0;
/* We will be inserting new insns "backwards". If we are to insert
after INSN, find the next insn, and insert before it. */
*************** change_stack (insn, old, new, where)
*** 2160,2244 ****
insn = NEXT_INSN (insn);
}
! /* Pop any registers that are not needed in the new block. */
!
! for (reg = old->top; reg >= 0; reg--)
! if (! TEST_HARD_REG_BIT (new->reg_set, old->reg[reg]))
! emit_pop_insn (insn, old, FP_MODE_REG (old->reg[reg], DFmode),
! EMIT_BEFORE);
! if (new->top == -2)
{
! /* If the new block has never been processed, then it can inherit
! the old stack order. */
! new->top = old->top;
! memcpy (new->reg, old->reg, sizeof (new->reg));
}
- else
- {
- /* This block has been entered before, and we must match the
- previously selected stack order. */
! /* By now, the only difference should be the order of the stack,
! not their depth or liveliness. */
! GO_IF_HARD_REG_EQUAL (old->reg_set, new->reg_set, win);
! abort ();
! win:
! if (old->top != new->top)
! abort ();
! /* If the stack is not empty (new->top != -1), loop here emitting
! swaps until the stack is correct.
! The worst case number of swaps emitted is N + 2, where N is the
! depth of the stack. In some cases, the reg at the top of
! stack may be correct, but swapped anyway in order to fix
! other regs. But since we never swap any other reg away from
! its correct slot, this algorithm will converge. */
! if (new->top != -1)
! do
! {
! /* Swap the reg at top of stack into the position it is
! supposed to be in, until the correct top of stack appears. */
! while (old->reg[old->top] != new->reg[new->top])
! {
! for (reg = new->top; reg >= 0; reg--)
! if (new->reg[reg] == old->reg[old->top])
! break;
! if (reg == -1)
! abort ();
! emit_swap_insn (insn, old,
! FP_MODE_REG (old->reg[reg], DFmode));
! }
! /* See if any regs remain incorrect. If so, bring an
! incorrect reg to the top of stack, and let the while loop
! above fix it. */
! for (reg = new->top; reg >= 0; reg--)
! if (new->reg[reg] != old->reg[reg])
! {
! emit_swap_insn (insn, old,
! FP_MODE_REG (old->reg[reg], DFmode));
! break;
! }
! } while (reg >= 0);
! /* At this point there must be no differences. */
! for (reg = old->top; reg >= 0; reg--)
! if (old->reg[reg] != new->reg[reg])
! abort ();
! }
! if (update_end)
! current_block->end = PREV_INSN (insn);
}
/* Print stack configuration. */
--- 2195,2302 ----
insn = NEXT_INSN (insn);
}
! /* This algorithm generates minimal necesary amount of pop+swap instructions
! for fully defined regmaps.
! Pretty easy proof left ar excercise to the reader. Thinks may become tricker
! once fcompp and ffreep comes into play. Because this algorithm prefer
! top of stack pops, it should generate optimal code there too. */
! while (old->top >= 0)
{
! int reg = old->reg[old->top];
! int newpos = regmap[reg];
!
! /* Register is not present in new one - pop it. */
! if (newpos == -1)
! {
! emit_pop_insn (insn, old, FP_MODE_REG (reg, DFmode),
! EMIT_BEFORE);
! ninsns++;
! continue;
! }
! /* Register is in place now. Check corectness of whole stack to see
! what work is left to do. Prefer cycles because then we get the
! top of stack returned. */
! if (newpos == old->top)
! {
! newpos = find_cycle (regmap, old);
! if (newpos < 0)
! newpos = find_path (regmap, old);
! if (newpos < 0)
! break;
! }
! /* When position is not defined, prefer paths, because new possition
! of the register doesn't matter. */
! if (newpos == -2)
! {
! newpos = find_path (regmap, old);
! if (newpos < 0)
! newpos = find_cycle (regmap, old);
! if (newpos < 0)
! break;
! }
! if (regmap[(int) old->reg[newpos]] != -1)
! emit_swap_insn (insn, old, FP_MODE_REG (old->reg[newpos], DFmode));
! else
! emit_pop_insn (insn, old, FP_MODE_REG (old->reg[newpos], DFmode), EMIT_BEFORE);
! ninsns++;
}
! /* Check that new stack really match old one. */
! if (update_end)
! current_block->end = PREV_INSN (insn);
! return ninsns;
! }
! /* Emit code to change stack from OLD to NEW. Some registers might have
! to be popped, but there can never become live.
! Insert any needed insns before or after INSN, as indicated by
! WHERE. OLD is the original stack layout, and NEW is the desired
! form. OLD is updated to reflect the code emitted, ie, it will be
! the same as NEW upon return.
! */
! static int
! change_stack (insn, old, new, where)
! rtx insn;
! stack old;
! stack new;
! enum emit_where where;
! {
! int reg;
! int ninsns = 0;
! int regmap [LAST_STACK_REG+1];
! /* Stack ought to be initialized now. */
! if (new->top == -2 || new->top == -2)
! abort ();
! GO_IF_HARD_REG_SUBSET (new->reg_set, old->reg_set, win1);
! abort ();
! win1:
! for (reg = FIRST_STACK_REG ; reg <= LAST_STACK_REG + 1 ; reg++)
! regmap [reg] = -1;
! for (reg = 0 ; reg <= new->top ; reg++)
! regmap [(int) new->reg[reg]] = reg;
! ninsns = change_to_regmap (insn, old, regmap, where);
! GO_IF_HARD_REG_EQUAL (old->reg_set, new->reg_set, win2);
! abort ();
! win2:
! if (old->top != new->top)
! abort ();
! for (reg = old->top; reg >= 0; reg--)
! if (old->reg[reg] != new->reg[reg])
! abort ();
! return ninsns;
}
/* Print stack configuration. */
More information about the Gcc-patches
mailing list