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

[Zhenqiang Chen <zhenqiang dot chen at linaro dot org>]

On 10 June 2014 19:16, Steven Bosscher <stevenb.gcc@gmail.com> 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
-          heuristics is also in difficulties to evaluate accurately
-          spill cost at this stage.  */
+      if ((size_cost == -1)
+         && (comp_cost <= spill_cost))
        return -1;
       else
        size_cost = 0;