Discussion:
[PATCH Version 2][RFA]Improving register pressure directed hoist
(too old to reply)
Bin Cheng
2012-11-02 08:34:57 UTC
Permalink
Hi,
I posted a patch improving register pressure directed hoist at
http://gcc.gnu.org/ml/gcc-patches/2012-10/msg02552.html
Turns out it has a mistake in update_bb_reg_pressure resulting in changing
register pressure incorrectly. Here comes the 2nd version patch for review.
Unfortunately and strangely, this correct patch isn't as good as the bogus
one. The improvement is as below:

improvement
Thumb1 0.17% (0.13% before)
ARM 0.15% (0.12% before)
AARCH64 0.33%
MIPS 0.24%
PowerPC 0.62%
Thumb2 X
x86 X
x86_64 X
X means no obvious effect on the corresponding target.

Though the effect is not as good as expected, I still think it worth to be
reviewed, because:
a) it does improve code size a little bit on ARM target and introduces
fewer regression.
b) it makes further optimization possible (for example, computing VBE
optimistically in compute_code_hoist_vbeinout).

Also I don't understand why the bogus patch can catch more hoist
opportunities and improve code size, so please help if you have any idea
about this.

It is re-tested on x86. OK?

Thanks very much.


2012-11-02 Bin Cheng <***@arm.com>

* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.

gcc/testsuite/ChangeLog
2012-11-02 Bin Cheng <***@arm.com>

* gcc.dg/hoist-register-pressure-3.c: New test.
Jeff Law
2012-11-05 20:50:55 UTC
Permalink
Post by Bin Cheng
Also I don't understand why the bogus patch can catch more hoist
opportunities and improve code size, so please help if you have any idea
about this.
Well, perturbing the code, particularly in a way which is supposed to
change the amount of register pressure is certainly going to affect the
allocators and reload.

It shouldn't be that hard to look at results which differ between the
two patches and analyze why they're different.
Post by Bin Cheng
* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.
gcc/testsuite/ChangeLog
* gcc.dg/hoist-register-pressure-3.c: New test.
+/* Update register pressure for BB when hoisting an expression from
+ instruction FROM, if live ranges of inputs are shrunk. Also
+ maintain live_in information if live range of register referred
+ in FROM is shrunk.
+
+ Return 0 if register pressure doesn't change, otherwise return
+ the number by which register pressure is decreased.
+
+ NOTE: Register pressure won't be increased in this function. */
+
+static int
+update_bb_reg_pressure (basic_block bb, rtx from,
+ enum reg_class pressure_class, int nregs)
+{
+ rtx dreg, insn;
+ basic_block succ_bb;
+ df_ref *op, op_ref;
+ edge succ;
+ edge_iterator ei;
+ int decreased_pressure = 0;
+
+ for (op = DF_INSN_USES (from); *op; op++)
+ {
+ dreg = DF_REF_REAL_REG (*op);
+ 1. referred on any path from the end of this block to EXIT, or
+ 2. referred by insns other than FROM in this block. */
+ FOR_EACH_EDGE (succ, ei, bb->succs)
+ {
+ succ_bb = succ->dest;
+ if (succ_bb == EXIT_BLOCK_PTR)
+ continue;
+
+ if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
+ break;
+ }
+ if (succ != NULL)
+ continue;
+
+ op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
+ for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
+ {
+ if (!DF_REF_INSN_INFO (op_ref))
+ continue;
+
+ insn = DF_REF_INSN (op_ref);
+ if (BLOCK_FOR_INSN (insn) == bb
+ && NONDEBUG_INSN_P (insn) && insn != from)
+ break;
+ }
+
+ /* Decrease register pressure and update live_in information for
+ this block. */
+ if (!op_ref)
+ {
+ decreased_pressure += nregs;
+ BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
+ bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
+ }
+ }
+ return decreased_pressure;
So we're looking to see if any of the registers used in FROM are used
after from. If none are used, then we decrease the register pressure by
nregs which appears to be a property of the the registers *set* in FROM.
Is seems like there's some inconsistency here. Or have I
misunderstood something?

I'm not sure how much it matters in practice, except perhaps for
conversions and the like where the source and destination operands are
different modes.
jeff
Bin Cheng
2012-11-06 13:03:51 UTC
Permalink
-----Original Message-----
Sent: Tuesday, November 06, 2012 4:51 AM
To: Bin Cheng
Subject: Re: [PATCH Version 2][RFA]Improving register pressure directed
hoist
Post by Bin Cheng
Also I don't understand why the bogus patch can catch more hoist
opportunities and improve code size, so please help if you have any
idea about this.
Well, perturbing the code, particularly in a way which is supposed to
change
the amount of register pressure is certainly going to affect the
allocators
and reload.
It shouldn't be that hard to look at results which differ between the two
patches and analyze why they're different.
I will try to investigate this issue.
Post by Bin Cheng
* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.
gcc/testsuite/ChangeLog
* gcc.dg/hoist-register-pressure-3.c: New test.
+/* Update register pressure for BB when hoisting an expression from
+ instruction FROM, if live ranges of inputs are shrunk. Also
+ maintain live_in information if live range of register referred
+ in FROM is shrunk.
+
+ Return 0 if register pressure doesn't change, otherwise return
+ the number by which register pressure is decreased.
+
+ NOTE: Register pressure won't be increased in this function. */
+
+static int
+update_bb_reg_pressure (basic_block bb, rtx from,
+ enum reg_class pressure_class, int nregs) {
+ rtx dreg, insn;
+ basic_block succ_bb;
+ df_ref *op, op_ref;
+ edge succ;
+ edge_iterator ei;
+ int decreased_pressure = 0;
+
+ for (op = DF_INSN_USES (from); *op; op++)
+ {
+ dreg = DF_REF_REAL_REG (*op);
+ 1. referred on any path from the end of this block to EXIT, or
+ 2. referred by insns other than FROM in this block. */
+ FOR_EACH_EDGE (succ, ei, bb->succs)
+ {
+ succ_bb = succ->dest;
+ if (succ_bb == EXIT_BLOCK_PTR)
+ continue;
+
+ if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
+ break;
+ }
+ if (succ != NULL)
+ continue;
+
+ op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
+ for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
+ {
+ if (!DF_REF_INSN_INFO (op_ref))
+ continue;
+
+ insn = DF_REF_INSN (op_ref);
+ if (BLOCK_FOR_INSN (insn) == bb
+ && NONDEBUG_INSN_P (insn) && insn != from)
+ break;
+ }
+
+ /* Decrease register pressure and update live_in information for
+ this block. */
+ if (!op_ref)
+ {
+ decreased_pressure += nregs;
+ BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
+ bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
+ }
+ }
+ return decreased_pressure;
So we're looking to see if any of the registers used in FROM are used
after
from. If none are used, then we decrease the register pressure by nregs
which
appears to be a property of the the registers *set* in FROM.
Is seems like there's some inconsistency here. Or have I misunderstood
something?
I'm not sure how much it matters in practice, except perhaps for
conversions
and the like where the source and destination operands are different
modes.

Agreed, I missed the inconsistence of register_class/number between input
and output. I will fix this issue and measure the effect once I get back to
office.

Thanks for your comments.
Bin Cheng
2012-11-07 21:05:05 UTC
Permalink
-----Original Message-----
On
Behalf Of Bin Cheng
Sent: Tuesday, November 06, 2012 9:04 PM
To: 'Jeff Law'
Subject: RE: [PATCH Version 2][RFA]Improving register pressure directed
hoist
-----Original Message-----
Sent: Tuesday, November 06, 2012 4:51 AM
To: Bin Cheng
Subject: Re: [PATCH Version 2][RFA]Improving register pressure
directed
hoist
Post by Bin Cheng
Also I don't understand why the bogus patch can catch more hoist
opportunities and improve code size, so please help if you have any
idea about this.
Well, perturbing the code, particularly in a way which is supposed to
change
the amount of register pressure is certainly going to affect the
allocators
and reload.
It shouldn't be that hard to look at results which differ between the
two patches and analyze why they're different.
I will try to investigate this issue.
Post by Bin Cheng
* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.
gcc/testsuite/ChangeLog
* gcc.dg/hoist-register-pressure-3.c: New test.
+/* Update register pressure for BB when hoisting an expression from
+ instruction FROM, if live ranges of inputs are shrunk. Also
+ maintain live_in information if live range of register referred
+ in FROM is shrunk.
+
+ Return 0 if register pressure doesn't change, otherwise return
+ the number by which register pressure is decreased.
+
+ NOTE: Register pressure won't be increased in this function. */
+
+static int
+update_bb_reg_pressure (basic_block bb, rtx from,
+ enum reg_class pressure_class, int nregs) {
+ rtx dreg, insn;
+ basic_block succ_bb;
+ df_ref *op, op_ref;
+ edge succ;
+ edge_iterator ei;
+ int decreased_pressure = 0;
+
+ for (op = DF_INSN_USES (from); *op; op++)
+ {
+ dreg = DF_REF_REAL_REG (*op);
+ 1. referred on any path from the end of this block to EXIT, or
+ 2. referred by insns other than FROM in this block. */
+ FOR_EACH_EDGE (succ, ei, bb->succs)
+ {
+ succ_bb = succ->dest;
+ if (succ_bb == EXIT_BLOCK_PTR)
+ continue;
+
+ if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
+ break;
+ }
+ if (succ != NULL)
+ continue;
+
+ op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
+ for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
+ {
+ if (!DF_REF_INSN_INFO (op_ref))
+ continue;
+
+ insn = DF_REF_INSN (op_ref);
+ if (BLOCK_FOR_INSN (insn) == bb
+ && NONDEBUG_INSN_P (insn) && insn != from)
+ break;
+ }
+
+ /* Decrease register pressure and update live_in information for
+ this block. */
+ if (!op_ref)
+ {
+ decreased_pressure += nregs;
+ BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
+ bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
+ }
+ }
+ return decreased_pressure;
So we're looking to see if any of the registers used in FROM are used
after
from. If none are used, then we decrease the register pressure by
nregs
which
appears to be a property of the the registers *set* in FROM.
Is seems like there's some inconsistency here. Or have I
misunderstood something?
I'm not sure how much it matters in practice, except perhaps for
conversions
and the like where the source and destination operands are different
modes.
Agreed, I missed the inconsistence of register_class/number between input
and
output. I will fix this issue and measure the effect once I get back to
office.
Hi Jeff,
I modified the patch updating reg_class/num of input registers, rather than
output register. The code size info collected shows no obvious change from
last patch.
Bootstrapped on x86, tested on x86-linux and arm-none-eabi/Thumb1. Is it OK?

Thanks


2012-11-08 Bin Cheng <***@arm.com>

* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.

gcc/testsuite/ChangeLog
2012-11-08 Bin Cheng <***@arm.com>

* gcc.dg/hoist-register-pressure-3.c: New test.
Jeff Law
2012-11-09 13:57:36 UTC
Permalink
Post by Bin Cheng
* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.
gcc/testsuite/ChangeLog
* gcc.dg/hoist-register-pressure-3.c: New test.
Thanks for taking care of that inconsistency. This is OK to install now.

Thanks,
jeff
Bin Cheng
2012-11-12 02:25:29 UTC
Permalink
-----Original Message-----
Sent: Friday, November 09, 2012 9:58 PM
To: Bin Cheng
Subject: Re: [PATCH Version 2][RFA]Improving register pressure directed
hoist
Post by Bin Cheng
* gcse.c: (struct bb_data): Add new fields, old_pressure, live_in
and backup.
(calculate_bb_reg_pressure): Initialize live_in and backup.
(update_bb_reg_pressure): New.
(should_hoist_expr_to_dom): Add new parameter from.
Monitor the change of reg pressure and use it to drive hoisting.
(hoist_code): Update LIVE and reg pressure information.
gcc/testsuite/ChangeLog
* gcc.dg/hoist-register-pressure-3.c: New test.
Thanks for taking care of that inconsistency. This is OK to install now.
Hi Jeff & Jakub,
Thanks for reviewing.

I posted in the below message explaining that I want to include this patch
in GCC 4.8.
http://gcc.gnu.org/ml/gcc/2012-10/msg00471.html

Since it is approved now, I committed it as r193425 in TRUNK.

Thanks.

Loading...