[LLVMdev] Question regarding basic-block placement optimization

[Chandler Carruth]

On Tue, Oct 18, 2011 at 6:58 PM, Jakob Stoklund Olesen <stoklund at 2pi.dk>wrote:

>
> On Oct 18, 2011, at 5:22 PM, Chandler Carruth wrote:
>
> As for why it should be an IR pass, mostly because once the selection dag
>> runs through the code, we can never recover all of the freedom we have at
>> the IR level. To start with, splicing MBBs around requires known about the
>> terminators (which we only some of the time do), and it requires re-writing
>> them a touch to account for the different fall-through pattern. To make
>> matters worse, at this point we don't have the nicely analyzable 'switch'
>> terminator (I think), and so the existing MBB placement code just bails on
>> non-branch-exit blocks.
>>
>>
>> Those are all the wrong reasons for not doing the right thing.
>>
>
> Sorry, I'm not trying to do the wrong thing because of this... Currently,
> it feels like a trade-off in terms of cost/benefit. It's not yet clear to me
> that the benefit of doing this analysis in the CodeGen layer outweighs the
> cost and I was trying to clarify what the costs I perceive are.
>
>
> I think it's mostly about understanding how MBBs work.
>

Indeed, that seems to be the case. =D Thanks for explaining things below, it
helped me a lot.


> Ignoring calls and returns, most machines have three kinds of branches:
>
> 1. Unconditional
> 2. Conditional
> 3. Indirect.
>
> The AnalyzeBranch() function understands the first two kinds, so if that
> function returns false (as in it's false that it didn't succeed) you can
> move the successors around, and you know that placing a successor
> immediately after the block and calling updateTerminator() will give you a
> fall-through.
>
> If AnalyzeBranch() fails, you can still check if the last instruction in
> the block is an unpredicated barrier. If so, it is still safe to move the
> successors around, but that block will never be a fall-through. The
> canFallThrough() function implements this check.
>
> If the last instruction in the block is predicated or not a barrier, you
> must keep it together with its layout successor. This should only happen in
> rare cases where it is necessary. For example, I am planning to lower invoke
> instructions into call instructions that are terminators. This is necessary
> to accurately model control flow to landing pads. Such a call instruction
> must fall through to its layout successor.
>
> Some experimental targets don't implement AnalyzeBranch, so everything
> looks like an indirect branch. Those targets get the code placement they
> deserve.
>
> I am not claiming the API is awesome, but the information you need is
> there, and you have the same freedom as for IR.
>
> We explicitly designed the branch weights so switch lowering could annotate
> all the new branches with exact weights. It would be a shame to ignore that
> information.
>
> So the benefits are:
>
> - Profile-driven fall-through layout of lowered switches. That should be a
> pretty big deal.
> - Proper placement of split critical edges.
> - The ability to implement stuff like: "Don't put too many branches in a
> fetch group, or you'll freak out the branch predictor".
>

These all seem like really good reasons, and your explanation helps me a
lot. I'll take a stab at re-implementing this on MBBs. In the mean time,
I've attached my patch with the IR-level patch as most of the interesting
logic will remain the same. Please be gentle, it's my first proper LLVM
pass, and my knowledge of optimization pass research & papers is limited.
The part I'm least pleased with is the computation of weight for each chain
in an SCC of chains, but so far I've not come up with anything better. =]
I've tested this on several ad-hoc test cases, but nothing really thorough.
Going to try moving it to the codegen layer first.


One question that remains, mostly to ensure I've understood you correctly:
For switches, it is represented as an N-ary conditional terminator, and the
targets of the switch can be freely intermingled with other MBBs?

I'll attach an updated patch to work on MBBs when I have one...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111019/bbb9144a/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: block_placement_ir.patch
Type: text/x-patch
Size: 24170 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111019/bbb9144a/attachment.bin>