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
