[Committed]: [PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-07-02 Thread Zhenqiang Chen 
On 2 July 2014 03:54, Jeff Law  wrote:
> On 07/01/14 01:16, Zhenqiang Chen wrote:
>
>>
>> ChangeLog:
>> 2014-07-01  Zhenqiang Chen  
>>
>>  * loop-invariant.c (struct invariant): Add a new member: eqno;
>>  (find_identical_invariants): Update eqno;
>>  (create_new_invariant): Init eqno;
>>  (get_inv_cost): Compute comp_cost wiht eqno;
>
> s/wiht/with/
>
> Do you have a testcase for this?  If at all possible I'd like to see some
> kind of test to verify that this tracking results in better invariant
> selection.

Since the patch bases on the result of rtx_cost, it is hard to design
a common test case. A testcase for ARM is added.

> With some kind of test and the ChangeLog typo fixed, this is OK.

Thanks. Updated and committed @r212256.

ChangeLog:
2014-07-03  Zhenqiang Chen  

* loop-invariant.c (struct invariant): Add a new member: eqno;
(find_identical_invariants): Update eqno;
(create_new_invariant): Init eqno;
(get_inv_cost): Compute comp_cost with eqno;


testsuite/ChangeLog:
2014-07-03  Zhenqiang Chen  

* gcc.target/arm/identical-invariants.c: New test.

diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index d47d461..bd67eb9 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -104,6 +104,9 @@ struct invariant
   /* The number of the invariant with the same value.  */
   unsigned eqto;

+  /* The number of invariants which eqto this.  */
+  unsigned eqno;
+
   /* If we moved the invariant out of the loop, the register that contains its
  value.  */
   rtx reg;
@@ -498,6 +501,7 @@ find_identical_invariants (invariant_htab_type
*eq, struct invariant *inv)
   struct invariant *dep;
   rtx expr, set;
   enum machine_mode mode;
+  struct invariant *tmp;

   if (inv->eqto != ~0u)
 return;
@@ -513,7 +517,12 @@ find_identical_invariants (invariant_htab_type
*eq, struct invariant *inv)
   mode = GET_MODE (expr);
   if (mode == VOIDmode)
 mode = GET_MODE (SET_DEST (set));
-  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
+
+  tmp = find_or_insert_inv (eq, expr, mode, inv);
+  inv->eqto = tmp->invno;
+
+  if (tmp->invno != inv->invno && inv->always_executed)
+tmp->eqno++;

   if (dump_file && inv->eqto != inv->invno)
 fprintf (dump_file,
@@ -1136,7 +1149,7 @@ get_inv_cost (struct invariant *inv, int
*comp_cost, unsigned *regs_needed,

   if (!inv->cheap_address
   || inv->def->n_addr_uses < inv->def->n_uses)
-(*comp_cost) += inv->cost;
+(*comp_cost) += inv->cost * inv->eqno;

 #ifdef STACK_REGS
   {
diff --git a/gcc/testsuite/gcc.target/arm/identical-invariants.c
b/gcc/testsuite/gcc.target/arm/identical-invariants.c
new file mode 100644
index 000..7762ce6
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/identical-invariants.c
@@ -0,0 +1,29 @@
+/* { dg-do compile { target { arm_thumb2_ok } } } */
+/* { dg-options "-O2 -fdump-rtl-loop2_invariant " } */
+
+int t1, t2, t3, t4, t5, t6, t7, t8, t9, t10;
+extern void foo2 (int *, int *, int *, int *, int *, int *);
+extern int foo3 (int, int, int, int, int, int);
+int foo (int a, int b, int c, int d)
+{
+   int i = a;
+
+   for (; i > 0; i += b)
+{
+  if (a > 0x1234567)
+   foo2 (&t1, &t2, &t3, &t4, &t5, &t6);
+  foo2 (&t1, &t2, &t3, &t4, &t5, &t6);
+  if (b > 0x1234567)
+   foo2 (&t7, &t2, &t8, &t4, &t5, &t6);
+  foo2 (&t1, &t2, &t3, &t4, &t5, &t6);
+  if (c > 0x1234567)
+   foo2 (&t1, &t9, &t10, &t4, &t5, &t6);
+  t2 = t5 - d;
+}
+
+ return foo3 (t1, t2, t3, t4, t5, t6);
+}
+
+/* { dg-final { scan-rtl-dump "Decided to move invariant 0"
"loop2_invariant" } } */
+/* { dg-final { cleanup-rtl-dump "loop2_invariant" } } */
+

Re: [PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-07-01 Thread Jeff Law 

On 07/01/14 01:16, Zhenqiang Chen wrote:



ChangeLog:
2014-07-01  Zhenqiang Chen  

 * loop-invariant.c (struct invariant): Add a new member: eqno;
 (find_identical_invariants): Update eqno;
 (create_new_invariant): Init eqno;
 (get_inv_cost): Compute comp_cost wiht eqno;

s/wiht/with/

Do you have a testcase for this?  If at all possible I'd like to see 
some kind of test to verify that this tracking results in better 
invariant selection.


With some kind of test and the ChangeLog typo fixed, this is OK.

jeff

Re: [PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-07-01 Thread Zhenqiang Chen 
On 10 June 2014 19:16, Steven Bosscher  wrote:
> On Tue, Jun 10, 2014 at 11:23 AM, Zhenqiang Chen wrote:
>> * loop-invariant.c (struct invariant): Add a new member: eqno;
>> (find_identical_invariants): Update eqno;
>> (create_new_invariant): Init eqno;
>> (get_inv_cost): Compute comp_cost wiht eqno;
>> (gain_for_invariant): Take spill cost into account.
>
> Look OK except ...
>
>> @@ -1243,7 +1256,13 @@ gain_for_invariant (struct invariant *inv,
>> unsigned *regs_needed,
>>  + IRA_LOOP_RESERVED_REGS
>>  - ira_class_hard_regs_num[cl];
>>if (size_cost > 0)
>> -   return -1;
>> +   {
>> + int spill_cost = target_spill_cost [speed] * (int) regs_needed[cl];
>> + if (comp_cost <= spill_cost)
>> +   return -1;
>> +
>> + return 2;
>> +   }
>>else
>> size_cost = 0;
>>  }
>
> ... why "return 2", instead of just falling through to "return
> comp_cost - size_cost;"?

The updated patch removes the check on spill cost since the check
seams not sound and tests show it does not help much on the result.

Bootstrap and no make check regression on X86-64.

OK for trunk?

Thanks!
-Zhenqiang

ChangeLog:
2014-07-01  Zhenqiang Chen  

* loop-invariant.c (struct invariant): Add a new member: eqno;
(find_identical_invariants): Update eqno;
(create_new_invariant): Init eqno;
(get_inv_cost): Compute comp_cost wiht eqno;

diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index d47d461..bd67eb9 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -104,6 +104,9 @@ struct invariant
   /* The number of the invariant with the same value.  */
   unsigned eqto;

+  /* The number of invariants which eqto this.  */
+  unsigned eqno;
+
   /* If we moved the invariant out of the loop, the register that contains its
  value.  */
   rtx reg;
@@ -498,6 +501,7 @@ find_identical_invariants (invariant_htab_type
*eq, struct invariant *inv)
   struct invariant *dep;
   rtx expr, set;
   enum machine_mode mode;
+  struct invariant *tmp;

   if (inv->eqto != ~0u)
 return;
@@ -513,7 +517,12 @@ find_identical_invariants (invariant_htab_type
*eq, struct invariant *inv)
   mode = GET_MODE (expr);
   if (mode == VOIDmode)
 mode = GET_MODE (SET_DEST (set));
-  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
+
+  tmp = find_or_insert_inv (eq, expr, mode, inv);
+  inv->eqto = tmp->invno;
+
+  if (tmp->invno != inv->invno && inv->always_executed)
+tmp->eqno++;

   if (dump_file && inv->eqto != inv->invno)
 fprintf (dump_file,
@@ -722,6 +731,10 @@ create_new_invariant (struct def *def, rtx insn,
bitmap depends_on,

   inv->invno = invariants.length ();
   inv->eqto = ~0u;
+
+  /* Itself.  */
+  inv->eqno = 1;
+
   if (def)
 def->invno = inv->invno;
   invariants.safe_push (inv);
@@ -1136,7 +1149,7 @@ get_inv_cost (struct invariant *inv, int
*comp_cost, unsigned *regs_needed,

   if (!inv->cheap_address
   || inv->def->n_addr_uses < inv->def->n_uses)
-(*comp_cost) += inv->cost;
+(*comp_cost) += inv->cost * inv->eqno;

 #ifdef STACK_REGS
   {

Re: [PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-06-17 Thread Zhenqiang Chen 
On 10 June 2014 19:16, Steven Bosscher  wrote:
> On Tue, Jun 10, 2014 at 11:23 AM, Zhenqiang Chen wrote:
>> * loop-invariant.c (struct invariant): Add a new member: eqno;
>> (find_identical_invariants): Update eqno;
>> (create_new_invariant): Init eqno;
>> (get_inv_cost): Compute comp_cost wiht eqno;
>> (gain_for_invariant): Take spill cost into account.
>
> Look OK except ...
>
>> @@ -1243,7 +1256,13 @@ gain_for_invariant (struct invariant *inv,
>> unsigned *regs_needed,
>>  + IRA_LOOP_RESERVED_REGS
>>  - ira_class_hard_regs_num[cl];
>>if (size_cost > 0)
>> -   return -1;
>> +   {
>> + int spill_cost = target_spill_cost [speed] * (int) regs_needed[cl];
>> + if (comp_cost <= spill_cost)
>> +   return -1;
>> +
>> + return 2;
>> +   }
>>else
>> size_cost = 0;
>>  }
>
> ... why "return 2", instead of just falling through to "return
> comp_cost - size_cost;"?

Thanks for the comments. Updated.

As your comments for the previous patch, I should also check the
overlap between reg classes. So I change the logic to check spill
cost.

diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index 6e43b49..af0c95b 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -104,6 +104,9 @@ struct invariant
   /* The number of the invariant with the same value.  */
   unsigned eqto;

+  /* The number of invariants which eqto this.  */
+  unsigned eqno;
+
   /* If we moved the invariant out of the loop, the register that contains its
  value.  */
   rtx reg;
@@ -498,6 +501,7 @@ find_identical_invariants (invariant_htab_type eq,
struct invariant *inv)
   struct invariant *dep;
   rtx expr, set;
   enum machine_mode mode;
+  struct invariant *tmp;

   if (inv->eqto != ~0u)
 return;
@@ -513,7 +517,12 @@ find_identical_invariants (invariant_htab_type
eq, struct invariant *inv)
   mode = GET_MODE (expr);
   if (mode == VOIDmode)
 mode = GET_MODE (SET_DEST (set));
-  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
+
+  tmp = find_or_insert_inv (eq, expr, mode, inv);
+  inv->eqto = tmp->invno;
+
+  if (tmp->invno != inv->invno && inv->always_executed)
+tmp->eqno++;

   if (dump_file && inv->eqto != inv->invno)
 fprintf (dump_file,
@@ -725,6 +734,10 @@ create_new_invariant (struct def *def, rtx insn,
bitmap depends_on,

   inv->invno = invariants.length ();
   inv->eqto = ~0u;
+
+  /* Itself.  */
+  inv->eqno = 1;
+
   if (def)
 def->invno = inv->invno;
   invariants.safe_push (inv);
@@ -1141,7 +1154,7 @@ get_inv_cost (struct invariant *inv, int
*comp_cost, unsigned *regs_needed,

   if (!inv->cheap_address
   || inv->def->n_addr_uses < inv->def->n_uses)
-(*comp_cost) += inv->cost;
+(*comp_cost) += inv->cost * inv->eqno;

 #ifdef STACK_REGS
   {
@@ -1249,7 +1262,7 @@ gain_for_invariant (struct invariant *inv,
unsigned *regs_needed,
unsigned *new_regs, unsigned regs_used,
bool speed, bool call_p)
 {
-  int comp_cost, size_cost;
+  int comp_cost, size_cost = 0;
   enum reg_class cl;
   int ret;

@@ -1273,6 +1286,8 @@ gain_for_invariant (struct invariant *inv,
unsigned *regs_needed,
 {
   int i;
   enum reg_class pressure_class;
+  int spill_cost = 0;
+  int base_cost = target_spill_cost [speed];

   for (i = 0; i < ira_pressure_classes_num; i++)
{
@@ -1286,30 +1301,13 @@ gain_for_invariant (struct invariant *inv,
unsigned *regs_needed,
  + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
  + IRA_LOOP_RESERVED_REGS
  > ira_class_hard_regs_num[pressure_class])
-   break;
+   {
+ spill_cost += base_cost * (int) regs_needed[pressure_class];
+ size_cost = -1;
+   }
}
-  if (i < ira_pressure_classes_num)
-   /* There will be register pressure excess and we want not to
-  make this loop invariant motion.  All loop invariants with
-  non-positive gains will be rejected in function
-  find_invariants_to_move.  Therefore we return the negative
-  number here.
-
-  One could think that this rejects also expensive loop
-  invariant motions and this will hurt code performance.
-  However numerous experiments with different heuristics
-  taking invariant cost into account did not confirm this
-  assumption.  There are possible explanations for this
-  result:
-   o probably all expensive invariants were already moved out
- of the loop by PRE and gimple invariant motion pass.
-   o expensive invariant execution will be hidden by insn
- scheduling or OOO processor hardware because usually such
- invariants have a lot of freedom to be executed
- out-of-order.
-  Another reason for ignoring invariant cost vs spilling cost
-

Re: [PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-06-10 Thread Steven Bosscher 
On Tue, Jun 10, 2014 at 11:23 AM, Zhenqiang Chen wrote:
> * loop-invariant.c (struct invariant): Add a new member: eqno;
> (find_identical_invariants): Update eqno;
> (create_new_invariant): Init eqno;
> (get_inv_cost): Compute comp_cost wiht eqno;
> (gain_for_invariant): Take spill cost into account.

Look OK except ...

> @@ -1243,7 +1256,13 @@ gain_for_invariant (struct invariant *inv,
> unsigned *regs_needed,
>  + IRA_LOOP_RESERVED_REGS
>  - ira_class_hard_regs_num[cl];
>if (size_cost > 0)
> -   return -1;
> +   {
> + int spill_cost = target_spill_cost [speed] * (int) regs_needed[cl];
> + if (comp_cost <= spill_cost)
> +   return -1;
> +
> + return 2;
> +   }
>else
> size_cost = 0;
>  }

... why "return 2", instead of just falling through to "return
comp_cost - size_cost;"?

Ciao!
Steven

[PATCH, loop2_invariant, 2/2] Change heuristics for identical invariants

2014-06-10 Thread Zhenqiang Chen 
Hi,

When analysing logs of loop2-invariant of eembc, I found the same
invariant occurred lots of times in a loop. But it was not selected
since its cost was not high and register pressure was high. Logs show
performance improvement by giving them higher priority to move.

The patch changes the heuristics to move identical invariants:
* add a new member eqno, which records the number of invariants eqto the inv.
* set its cost to: inv->cost * inv->eqno;
* compare with spill_cost if register pressure is high.

Bootstrap and no make check regression on X86-64.
Bootstrap and no make check regression on X86-64 with
flag_ira_loop_pressure = true.

OK for trunk?

Thanks!
-Zhenqiang

ChangeLog:
2014-06-10  Zhenqiang Chen  

* loop-invariant.c (struct invariant): Add a new member: eqno;
(find_identical_invariants): Update eqno;
(create_new_invariant): Init eqno;
(get_inv_cost): Compute comp_cost wiht eqno;
(gain_for_invariant): Take spill cost into account.

diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index 92388f5..c43206a 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -104,6 +104,9 @@ struct invariant
   /* The number of the invariant with the same value.  */
   unsigned eqto;

+  /* The number of invariants which eqto this.  */
+  unsigned eqno;
+
   /* If we moved the invariant out of the loop, the register that contains its
  value.  */
   rtx reg;
@@ -498,6 +501,7 @@ find_identical_invariants (invariant_htab_type eq,
struct invariant *inv)
   struct invariant *dep;
   rtx expr, set;
   enum machine_mode mode;
+  struct invariant *tmp;

   if (inv->eqto != ~0u)
 return;
@@ -513,7 +517,12 @@ find_identical_invariants (invariant_htab_type
eq, struct invariant *inv)
   mode = GET_MODE (expr);
   if (mode == VOIDmode)
 mode = GET_MODE (SET_DEST (set));
-  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
+
+  tmp = find_or_insert_inv (eq, expr, mode, inv);
+  inv->eqto = tmp->invno;
+
+  if (tmp->invno != inv->invno && inv->always_executed)
+tmp->eqno++;

   if (dump_file && inv->eqto != inv->invno)
 fprintf (dump_file,
@@ -725,6 +734,10 @@ create_new_invariant (struct def *def, rtx insn,
bitmap depends_on,

   inv->invno = invariants.length ();
   inv->eqto = ~0u;
+
+  /* Itself.  */
+  inv->eqno = 1;
+
   if (def)
 def->invno = inv->invno;
   invariants.safe_push (inv);
@@ -1107,7 +1120,7 @@ get_inv_cost (struct invariant *inv, int
*comp_cost, unsigned *regs_needed,

   if (!inv->cheap_address
   || inv->def->n_addr_uses < inv->def->n_uses)
-(*comp_cost) += inv->cost;
+(*comp_cost) += inv->cost * inv->eqno;

 #ifdef STACK_REGS
   {
@@ -1243,7 +1256,13 @@ gain_for_invariant (struct invariant *inv,
unsigned *regs_needed,
 + IRA_LOOP_RESERVED_REGS
 - ira_class_hard_regs_num[cl];
   if (size_cost > 0)
-   return -1;
+   {
+ int spill_cost = target_spill_cost [speed] * (int) regs_needed[cl];
+ if (comp_cost <= spill_cost)
+   return -1;
+
+ return 2;
+   }
   else
size_cost = 0;
 }