OSDN Git Service

Codegen: MachineBlockPlacement Improve probability layout.
authorKyle Butt <kyle+llvm@iteratee.net>
Fri, 29 Jul 2016 18:09:28 +0000 (18:09 +0000)
committerKyle Butt <kyle+llvm@iteratee.net>
Fri, 29 Jul 2016 18:09:28 +0000 (18:09 +0000)
commit9f1f15e084f96083b51a7cc32fbaf3a3525584e2
treeff58ddf62878aa8fc8766ce7c8685fff46e0032e
parent02e59638f89097ed458cba853d1b551025edcab9
Codegen: MachineBlockPlacement Improve probability layout.

The following pattern was being layed out poorly:

              A
             / \
            B   C
           / \ / \
          D   E   ? (Doesn't matter)

Where A->B is far more likely than A->C, and prob(B->D) = prob(B->E)

The current algorithm gives:
A,B,C,E (D goes on worklist)

It does this even if C has a frequency count of 0. This patch
adjusts the layout calculation so that if freq(B->E) >> freq(C->E)
then we go ahead and layout E rather than C. Fallthrough half the time
is better than fallthrough never, or fallthrough very rarely. The
resulting layout is:

A,B,E, (C and D are in a worklist)

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@277187 91177308-0d34-0410-b5e6-96231b3b80d8
lib/CodeGen/MachineBlockPlacement.cpp
test/CodeGen/X86/block-placement.ll