[RFA] Implement register pressure directed hoist pass

Hi Jeff, Steven,

This is the updated patch according to your comments. The main changes
includes:
1. Enable the option for all target at Os level by default.
2. Add a target independent test case.
3. Add comments on how the algorithm works.
4. Simplify the calculation of register pressure info by using DF caches.

Jeff, as for accurately simulating the change of register pressure made by
hoisting expression, I explained a little in previous message. According to
observation, cases in which register pressure decreases are relatively rare,
so this patch does not implement it. I can continue to improve code hoisting
that way in the future.

I bootstrapped it on x86_64 and x86, also tested on x86_64/x86/arm.
I recollected size info for CSiBE on miscellaneous targets as following:
		improvement
ARM		0.12%
Thumb1		0.13%
mips		0.24%
powerpc	0.59%
Thumb2		X
x86		X
x86_64		X
(X means no obvious effect, unfortunately.)

Also, since this is the simplification of previous patch, I think there is
no slowdown in compilation.

Please review. Thanks.

And updated ChangeLog entry:

2012-10-11  Bin Cheng  <bin.cheng@arm.com>

	* common.opt (flag_ira_hoist_pressure): New.
	* doc/invoke.texi (-fira-hoist-pressure): Describe.
	* ira-costs.c (ira_set_pseudo_classes): New parameter.
	* ira.h: Update copyright dates.
	(ira_set_pseudo_classes): Update prototype.
	* haifa-sched.c (sched_init): Update call.
	* ira.c (ira): Update call.
	* regmove.c: Update copyright dates.
	(regmove_optimize): Update call.
	* loop-invariant.c: Update copyright dates.
	(move_loop_invariants): Update call.
	* gcse.c: Update copyright dates.
	(struct bb_data): New structure.
	(BB_DATA): New macro.
	(curr_bb, curr_reg_pressure): New static variables.
	(should_hoist_expr_to_dom): Rename from hoist_expr_reaches_here_p.
	Change parameter expr_index to expr.
	Change parameter visited.
	New parameters pressure_class, nregs and hoisted_bbs.
	Use reg pressure to determine the distance expr can be hoisted.
	(hoist_code): Use reg pressure to direct the hoist process.
	(get_regno_pressure_class, get_pressure_class_and_nregs)
	(change_pressure, calculate_bb_reg_pressure): New.
	(one_code_hoisting_pass): Calculate register pressure. Allocate
	and free data.

gcc/testsuite/ChangeLog
2012-10-11  Bin Cheng  <bin.cheng@arm.com>

	* testsuite/gcc.dg/hoist-register-pressure.c: New test.

> -----Original Message-----
> From: Jeff Law [mailto:law@redhat.com]
> Sent: Tuesday, October 02, 2012 8:58 PM
> To: Bin Cheng
> Cc: 'Steven Bosscher'; gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH RFA] Implement register pressure directed hoist pass
> 
> On 09/29/2012 12:37 AM, Bin Cheng wrote:
> > Hi Steven,
> >
> > This is the updated patch according to your comments. Please review.
> > I also re-collected code size data and found it is improved by about
> > 0.24% for mips, which is better than previous data. I believe this
> > should be caused by recent changes in trunk, rather than by using DF
> > caches to calculate register pressure.
> >
> > Thanks.
> >
> > 2012-09-29  Bin Cheng<bin.cheng@arm.com>
> >
> > 	* common.opt (flag_ira_hoist_pressure): New.
> > 	* doc/invoke.texi (-fira-hoist-pressure): Describe.
> > 	* ira-costs.c (ira_set_pseudo_classes): New parameter.
> > 	* ira.h (ira_set_pseudo_classes): Update prototype.
> > 	* haifa-sched.c (sched_init): Update call.
> > 	* ira.c (ira): Update call.
> > 	* regmove.c (regmove_optimize): Update call.
> > 	* loop-invariant.c (move_loop_invariants): Update call.
> > 	* gcse.c (struct bb_data): New structure.
> > 	(BB_DATA): New macro.
> > 	(curr_bb, curr_regs_live, curr_reg_pressure, regs_set)
> > 	(n_regs_set): New static variables.
> > 	(hoist_expr_reaches_here_p): Use reg pressure to determine the
> > 	distance expr can be hoisted.
> > 	(hoist_code): Use reg pressure to direct the hoist process.
> > 	(get_regno_pressure_class, get_pressure_class_and_nregs)
> > 	(change_pressure, mark_regno_live, mark_regno_death)
> > 	(mark_reg_death, mark_reg_store, calculate_bb_reg_pressure): New.
> > 	(one_code_hoisting_pass): Calculate register pressure. Free data.
> > 	* config/arm/arm.c (arm_option_override): Set
flag_ira_hoist_pressure
> > 	on Thumb1 when optimizing for size.
> >
> >
> > hoist-reg-pressure-20120929.txt
> > +@item -fira-hoist-pressure
> > +@opindex fira-hoist-pressure
> > +Use IRA to evaluate register pressure in hoist pass for decisions to
hoist
> > +expressions.  This option usually results in generation of smaller code
on
> > +RISC machines, but it can slow the compiler down.
> I wouldn't use CISC/RISC here; I'd just say it usually results in
> smaller code.
> 
> You need to update the copyright year in gcse.c, ira.h, regmove.c, and
> loop-invariant.c.
> 
> > +      /* Only decrease distance if bb has high register pressure or
EXPR
> > +	 is const expr, otherwise EXPR can be hoisted through bb without
> > +	 cost.  */
> ?!?  This comment makes no sense to me.  To accurately know how hoisting
> an expression affects pressure you have to look at the inputs and output
> and see how their lifetime has changed.
> 
> In general:
> 
> For inputs, hoisting *may* reduce pressure.  You really have to look at
> how the life of the input changes based on the new location of the insn.
>   For example, if the input's lifetime is unchanged (say perhaps because
> it was live after the insn we want to hoist), then hoisting will have no
> impact. Otherwise the input's life is shortened, but to know by how much
> you have to determine whether the new death of the input occurs (it may
> still die in the hoisted insn or it may die elsewhere).
> 
> For an output, hoisting will (effectively) always extend the lifetime.
> 
> I've speculated that the right way to deal with register pressure in
> code motion is to actually build the dependency graph and use that to
> guide the code motions.  I've never cobbled together any real code to do
> this though.
> 
> Can we find a better name for hoist_expr_reaches_here_p since it's no
> longer just dealing with reachability -- it has heuristics now for
> profitability as well.
> 
> > @@ -2863,7 +2909,8 @@ static int
> >     if (visited == NULL)
> >       {
> >         visited_allocated_locally = 1;
> > -      visited = XCNEWVEC (char, last_basic_block);
> > +      visited = sbitmap_alloc (last_basic_block);
> > +      sbitmap_zero (visited);
> >       }
> What's the purpose behind changing visited from a simple array to a
> sbitmap?  I'm not objecting, but would like to hear the rationale behind
> that change.  I'll also note it wasn't mentioned in the ChangeLog.
> 
> Similarly what's the rationale behind passing the expression itself
> rather than just its index?  I don't see where we need to use anything
> other than the index in this code.  And again, this change isn't
> mentioned in the ChangeLog.
> 
> > +  /* Considered invariant insns have only one set.  */
> > +  gcc_assert (set != NULL_RTX);
> > +  reg = SET_DEST (set);
> > +  if (GET_CODE (reg) == SUBREG)
> > +    reg = SUBREG_REG (reg);
> > +  if (MEM_P (reg))
> > +    {
> > +      *nregs = 0;
> > +      pressure_class = NO_REGS;
> > +    }
> Don't you need to look at the addresses within the MEM?
> 
> 
> 
> > Index: gcc/config/arm/arm.c
> > ===================================================================
> > --- gcc/config/arm/arm.c	(revision 191816)
> > +++ gcc/config/arm/arm.c	(working copy)
> > @@ -2021,6 +2021,11 @@ arm_option_override (void)
> >         && current_tune->num_prefetch_slots > 0)
> >       flag_prefetch_loop_arrays = 1;
> >
> > +  /* Enable register pressure hoist when optimizing for size on Thumb1
set.
> */
> > +  if (TARGET_THUMB1 && optimize_function_for_size_p (cfun)
> > +      && flag_ira_hoist_pressure == -1)
> > +    flag_ira_hoist_pressure = 1;
> I'd rather see this enabled for all targets when optimizing for size;
> that guarantees more testing.  Even if it doesn't help a particular
> target, as long as it isn't hurting we're better off enabling it.
> 
> I don't see any testsuite additions -- it'd really help long term to
> have some tests for this stuff.
> 
> You should address the issues noted above and repost for final review
> before likely integration.
> 
> 
> 
> jeff
>

[RFA] Implement register pressure directed hoist pass

Commit Message

Patch