Rewrite #3 of machine block placement. This is based somewhat on the
authorChandler Carruth <chandlerc@gmail.com>
Sun, 13 Nov 2011 11:20:44 +0000 (11:20 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Sun, 13 Nov 2011 11:20:44 +0000 (11:20 +0000)
commitdf234353fb396e84e7a3a1cdd94f73681e65bd88
treed685cc000869f6d97d01f92ffe3a131cb299e5ef
parent9eb674880b98cbeca0cd5b3f0265b77282d48b4a
Rewrite #3 of machine block placement. This is based somewhat on the
second algorithm, but only loosely. It is more heavily based on the last
discussion I had with Andy. It continues to walk from the inner-most
loop outward, but there is a key difference. With this algorithm we
ensure that as we visit each loop, the entire loop is merged into
a single chain. At the end, the entire function is treated as a "loop",
and merged into a single chain. This chain forms the desired sequence of
blocks within the function. Switching to a single algorithm removes my
biggest problem with the previous approaches -- they had different
behavior depending on which system triggered the layout. Now there is
exactly one algorithm and one basis for the decision making.

The other key difference is how the chain is formed. This is based
heavily on the idea Andy mentioned of keeping a worklist of blocks that
are viable layout successors based on the CFG. Having this set allows us
to consistently select the best layout successor for each block. It is
expensive though.

The code here remains very rough. There is a lot that needs to be done
to clean up the code, and to make the runtime cost of this pass much
lower. Very much WIP, but this was a giant chunk of code and I'd rather
folks see it sooner than later. Everything remains behind a flag of
course.

I've added a couple of tests to exercise the issues that this iteration
was motivated by: loop structure preservation. I've also fixed one test
that was exhibiting the broken behavior of the previous version.

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