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

["xinliangli at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

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