[LLVMdev] Question regarding basic-block placement optimization

[Chandler Carruth]

Hello,

I'm working on basic-block placement optimizations based on branch
probability information. I've run into a stumbling block though. One of the
existing passes to do this, essentially a dead pass 'block-placement'
operates on the IR, reordering the blocks of the function, and relying on
the code generator to preserve that order unless it has a reason to
rearrange it. This pass is entirely untested AFAICT, and it doesn't work any
more...

That said, I've replicated its functionality with a much updated
transformation algorithm (no longer O(N^2), and finds better orderings!) and
predicated it on the new frequency and probability information. It "works"
great, but it doesn't actually optimize anything. It re-arranges all the
blocks of the IR function, laying them out perfectly. And then the code
generation layer throws that away and seems to establish its own ordering
altogether.

What's the best approach here? Is ignoring the order of blocks in the IR
function desired behavior? (It does seem reasonable, it just seems to have
not always been that way, so I wondered.)

Should I sink my pass down to a codegen pass?

If this really should live as a CodeGen pass, then what should become of the
existing code-placement pass in the CodeGen layer? Currently that pass does
two things:
1) It aligns loop bodies. This seems like a completely separate concern,
although likely a good one to do after any other placement optimizations.
2) It rearranges very specific loop structures using very specific
heuristics. Some of these seem redundant in the presence of probability
based information, but others seem orthogonal. Honestly, I don't understand
any of this very well, so it's likely I'm just misreading it.

I'm a bit wary of implementing this in the CodeGen layer as I worry that the
layout of the MBBs and their various branches will have already made
assumptions regarding the structure and shape of the CFG of the function...
But it would also perhaps give more stability to the resulting orderings,
improving the benefits of the pass.

Thoughts?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111018/6535f897/attachment.html>