[Bug middle-end/35603] New: branch reordering with FDO

[Bug middle-end/35603] New: branch reordering with FDO

[xinliangli at gmail dot com]

Given code like:

if (C1)
{
B1:
   ..
}
else if (C2)
{
B2:
   ...
}

If edge profile indicates that B2 (Predicate: ^C1 AND C2 ) is hot but B1
(predicate: C1) is rarely executed, and if C1 and C2 are mutually exclusive so
that the following holds:

C1 AND C2 = FALSE

==> ^C1 OR ^C2 = TRUE 
==> ^C1 AND C2 = C2

Then evaluation of C2 can be hoisted so that B2's control dependence height is
reduced.  After branch sinking and dead branch elimination, we can get:

if (C2)
{
B2:
   ....
}
else if (C1)
{
B1:
   ...
}


//Example:

Compare the runtime with -DORIG and -DREORDER. Then build -DORIG version with
profile data, it should have similar runtime ad -DREORDER.


int compute(int ) __attribute__((noinline));
#ifdef ORIG
int compute(int i)
{
     int result = 0;

     if (i == 10)
         result = 20;
     else if (i == 9)
         result = 30;
     else if ( i== 8)
         result = 40;
     else if (i ==  1)
          result = 200;

     else if (i == 2)
           result = 300;
     else if (i == 3)
           result = 400;


     return result;
}
#elif defined (REORDER)
int compute(int i)
{
    int result = 0;

     if (__builtin_expect(i,3) ==  3)
          result = 400;
     else if (i == 2)
           result = 300;
     else if (i == 1)
           result = 200;
     else if (i == 10)
         result = 20;
     else if (i == 9)
         result = 30;
     else if ( i== 8)
         result = 40;

     return result;
}

#endif
int main()
{

   int i;
   long long s = 0;
   for (i = 0; i < 1000000000; i++)
   {

        if (__builtin_expect((i%7777)==0,0))
             s+= compute(1);
        else if (__builtin_expect((i%6666) == 0,0))
             s += compute(2);
        else s += compute(3);
   }


   return (int)s;

}


-- 
           Summary: branch reordering with FDO
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: xinliangli at gmail dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35603

[Bug middle-end/35603] branch reordering with FDO

[xinliangli at gmail dot com]

------- Comment #1 from xinliangli at gmail dot com  2008-03-16 05:06 -------
(In reply to comment #0)
> Given code like:
> 
> if (C1)
> {
> B1:
>    ..
> }
> else if (C2)
> {
> B2:
>    ...
> }
> 
> If edge profile indicates that B2 (Predicate: ^C1 AND C2 ) is hot but B1
> (predicate: C1) is rarely executed, and if C1 and C2 are mutually exclusive so
> that the following holds:
> 
> C1 AND C2 = FALSE
> 
> ==> ^C1 OR ^C2 = TRUE 
> ==> ^C1 AND C2 = C2
> 
> Then evaluation of C2 can be hoisted so that B2's control dependence height is
> reduced.  After branch sinking and dead branch elimination, we can get:
> 
> if (C2)
> {
> B2:
>    ....
> }
> else if (C1)
> {
> B1:
>    ...
> }
> 
> 
> //Example:
> 
> Compare the runtime with -DORIG and -DREORDER. Then build -DORIG version with
> profile data, it should have similar runtime ad -DREORDER.
> 
> 
> int compute(int ) __attribute__((noinline));
> #ifdef ORIG
> int compute(int i)
> {
>      int result = 0;
> 
>      if (i == 10)
>          result = 20;
>      else if (i == 9)
>          result = 30;
>      else if ( i== 8)
>          result = 40;
>      else if (i ==  1)
>           result = 200;
> 
>      else if (i == 2)
>            result = 300;
>      else if (i == 3)
>            result = 400;
> 
> 
>      return result;
> }
> #elif defined (REORDER)
> int compute(int i)
> {
>     int result = 0;
> 
>      if (__builtin_expect(i,3) ==  3)
>           result = 400;
>      else if (i == 2)
>            result = 300;
>      else if (i == 1)
>            result = 200;
>      else if (i == 10)
>          result = 20;
>      else if (i == 9)
>          result = 30;
>      else if ( i== 8)
>          result = 40;
> 
>      return result;
> }
> 
> #endif
> int main()
> {
> 
>    int i;
>    long long s = 0;
>    for (i = 0; i < 1000000000; i++)
>    {
> 
>         if (__builtin_expect((i%7777)==0,0))
>              s+= compute(1);
>         else if (__builtin_expect((i%6666) == 0,0))
>              s += compute(2);
>         else s += compute(3);
>    }
> 
> 
>    return (int)s;
> 
> }
> 




This optimization should also be extended to reorder CAND, COR expressions

if (C1 || C2 || C3 || C3) <-- the condtion that is most likely true should be
first for COR
{

}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35603

[Bug middle-end/35603] branch reordering with FDO

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2008-03-16 05:08 -------
Hmm, reorder basic blocks already takes into the edge probability.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35603

[Bug middle-end/35603] branch reordering with FDO

[xinliangli at gmail dot com]

------- Comment #3 from xinliangli at gmail dot com  2008-03-17 06:36 -------
(In reply to comment #2)
> Hmm, reorder basic blocks already takes into the edge probability.
> 

Yes, I checked that gcc is doing good job in code layout with FDO for better
icache utilization.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35603