[LLVMdev] Question regarding basic-block placement optimization

Sergei Larin slarin at codeaurora.org
Tue Oct 18 08:37:07 PDT 2011


Can you please elaborate on the following statement? 

>>” I've replicated its functionality with a much updated transformation algorithm (no longer O(N^2), and finds better orderings!)”

Is this a new algorithm or something you can refer to.  Thanks. 


From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Chandler Carruth
Sent: Tuesday, October 18, 2011 4:54 AM
To: LLVM Developers Mailing List
Subject: [LLVMdev] Question regarding basic-block placement optimization


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.


More information about the llvm-dev mailing list