[LLVMdev] Missed optimization with indirectbr terminator

[Frits van Bommel]

On 8 July 2011 09:05, John McCall <rjmccall at apple.com> wrote:
> On Jul 7, 2011, at 10:15 PM, Carlo Alberto Ferraris wrote:
>> I'll try to inspect the assembler. Just a quick thought in the mean time, in the snippet I posted, if the backedge pointed directly to %19, other optimizations would likely notice that the loop could be removed entirely and replaced with a single addition. Do you think the code generator is able to do this?
>
> I don't think anyone's taught the loop optimizations to work
> over indirect branches, but it's not impossible.  This specific
> case would be better fixed by teaching some existing pass,
> maybe JumpThreading, that an indirectbr on a phi with constant
> blockaddr operands can be usefully optimized.

Actually, jumpthreading already knows about indirectbr.

The problem is that JumpThreading refuses to thread across loop
headers (that is, the target blocks of backedges). It should have the
same problem with a phi of booleans and a conditional branch instead
of a phi of pointers and an indirectbr.

The comment above JumpThreading::FindLoopHeaders() explains the
current situation:

/// FindLoopHeaders - We do not want jump threading to turn proper loop
/// structures into irreducible loops.  Doing this breaks up the loop nesting
/// hierarchy and pessimizes later transformations.  To prevent this from
/// happening, we first have to find the loop headers.  Here we approximate this
/// by finding targets of backedges in the CFG.
///
/// Note that there definitely are cases when we want to allow threading of
/// edges across a loop header.  For example, threading a jump from outside the
/// loop (the preheader) to an exit block of the loop is definitely profitable.
/// It is also almost always profitable to thread backedges from within the loop
/// to exit blocks, and is often profitable to thread backedges to other blocks
/// within the loop (forming a nested loop).  This simple analysis is not rich
/// enough to track all of these properties and keep it up-to-date as the CFG
/// mutates, so we don't allow any of these transformations.

Note that the case discussed in this thread (a backedge to a block
within the loop) is mentioned as "often profitable", but that
JumpThreading simply doesn't know enough about loops to recognize it.


There are several ways to solve this, as I see it:
1) teach jumpthreading about loops,
2) teach some other pass that knows about loops how to thread backedges, or
3) introduce a whole new pass just for this purpose.