Re: [PATCH] Fix loop split incorrect count and probability

[Xionghu Luo <luoxhu@linux.ibm.com>]

On 2021/10/26 21:05, Jan Hubicka wrote:
>>>
> 
>> That said, likely the profile update cannot be done uniformly
>> for all blocks of a loop?
> 
> For the loop:
> 
> for (i = 0; i < n; i = inc (i))
>     {
>       if (ga)
>         ga = do_something ();
> }
> 
> to:
> 
>   for (i = 0; i < x; i = inc (i))
> {
>     if (true)
>          ga = do_something ();
>         if (!ga)
>           break;
> }
>   for (; i < n; i = inc (i))
> {
>     if (false)
>          ga = do_something ();
> }
> 
> If probability of if (ga) being true is p, then you indeed can scale the
> first loop by p and second loop by 1-p.
> 
> Imagine that loop has n iterations and it takes m iterations for ga to
> become false, then probability of if(ga) is m/n and you get frequencies
> with m=n*(m/n) for first loop and n-m=n*(1-n/m) for second loop.
> 
> Because the conditional becomes constant true, one needs to scale up the
> basic block guarded by the if (true) up by n/m to compensate for the
> change.  With that the udpate should be right.
> Ideally one can bypass scaling of basic block(s) containing
>  ga = do_something () since the scaling first scales down to m/n
> and then scale sup to m/n. Which may not combine to noop.
> Perhaps one wants to have a parameter specifying basic blocks on which
> the scaling is performed while duplicating for this?

Yes.  This is the patch I tried to fix the issue for the case you
pasted for loop split.

https://gcc.gnu.org/pipermail/gcc-patches/2021-August/576566.html


 5<---------------- 
 | \              |
 6-- 7            |
    |  \          |
    21  11->3     |
    | \           |
    19 20----------
    |
    12<----
    / |   |
3<-11 16-- 

with the patch, Loop 1's bb {5,6,7,21,20} is scaled to 33% * count, 
Loop 2's bb {12,16} is scaled to 66% * count,
especially, probability of edge 21->19 and 21->20 is fixed to 
(33%, 67%) instead of (100%, INV).


-  <bb 5> [local count: 955630225]:
+  <bb 5> [local count: 315357973]:
   # i_13 = PHI <i_10(20), 0(4)>
   # prephitmp_12 = PHI <prephitmp_5(20), pretmp_3(4)>
   if (prephitmp_12 != 0)
     goto <bb 6>; [33.00%]
   else
     goto <bb 7>; [67.00%]

-  <bb 6> [local count: 315357972]:
+  <bb 6> [local count: 104068130]:
   _2 = do_something ();
   ga = _2;

-  <bb 7> [local count: 955630225]:
+  <bb 7> [local count: 315357973]:
   # prephitmp_5 = PHI <prephitmp_12(5), _2(6)>
   i_10 = inc (i_13);
   if (n_7(D) > i_10)
     goto <bb 21>; [89.00%]
   else
     goto <bb 11>; [11.00%]

   <bb 11> [local count: 105119324]:
   goto <bb 3>; [100.00%]

-  <bb 21> [local count: 850510901]:
+  <bb 21> [local count: 280668596]:
   if (prephitmp_12 != 0)
-    goto <bb 20>; [100.00%]
+    goto <bb 20>; [33.00%]
   else
-    goto <bb 19>; [INV]
+    goto <bb 19>; [67.00%]

-  <bb 20> [local count: 850510901]:
+  <bb 20> [local count: 280668596]:
   goto <bb 5>; [100.00%]

-  <bb 19> [count: 0]:
+  <bb 19> [local count: 70429947]:
   # i_23 = PHI <i_10(21)>
   # prephitmp_25 = PHI <prephitmp_5(21)>

-  <bb 12> [local count: 955630225]:
+  <bb 12> [local count: 640272252]:
   # i_15 = PHI <i_23(19), i_22(16)>
   # prephitmp_16 = PHI <prephitmp_25(19), prephitmp_16(16)>
   i_22 = inc (i_15);
   if (n_7(D) > i_22)
     goto <bb 16>; [89.00%]
   else
     goto <bb 11>; [11.00%]

-  <bb 16> [local count: 850510901]:
+  <bb 16> [local count: 569842305]:
   goto <bb 12>; [100.00%]

> 
> Honza
>>
>> Richard.

-- 
Thanks,
Xionghu