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

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

------- 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