[LLVMdev] Simplifying selects + arm stuff

[Chris Lattner]

<cc'ing llvmdev>

On Nov 10, 2010, at 6:38 AM, Duncan Sands wrote:

> Hi Chris, in commit 12800 you introduced the following transform:
> 
>  Implement select.ll:test12*
> 
>  This transforms code like this:
> 
>     %C = or %A, %B
>     %D = select %cond, %C, %A
>  into:
>     %C = select %cond, %B, 0
>     %D = or %A, %C
> 
>  Since B is often a constant, the select can often be eliminated.  In any case,
>  this reduces the usage count of A, allowing subsequent optimizations to
>  happen.

Right, I still think this is goodness.

> 
> Now consider the following example:
> 
>  %z = and i32 %x, %y
>  %s = select i1 %cond, i32 %y, i32 %z
>  %r = and i32 %x, %s
> 
> Here %r could be simplified to
>  %r = and i32 %x, %y
> (i.e. the same as %z) so replaced with %z everywhere.
> 
> We even have logic to do this (ThreadBinOpOverSelect, which I just added) in
> InstructionSimplify.  The nice thing about InstructionSimplify is that it
> doesn't ever create any new instructions, so is pretty much always a win.
> The problem is that the logic never fires: your instcombine logic gets there
> first, and transforms the example into
> 
>  %z = select i1 %cond, i32 -1, i32 %x
>  %s = and i32 %z, %y
>  %r = and i32 %s, %x
> 
> which is not nearly as good.

Yeah, that's not nearly as good as "%r = and i32 %x, %y" :)

Note that:

 %z = select i1 %cond, i32 -1, i32 %x
 %s = and i32 %z, %y

Is a "conditional and".  It would be interesting to know if the ARM backend gets this as a single predicated 'and' instruction (similarly for the 'or' and 'xor' version of these patterns).  I bet not, which is bad if instcombine is canonicalizing this way.

> Do you have any thoughts for how to get the best of both worlds?  How about
> only applying your transform when one of the operands (eg B) is a constant?

I don't think that's a great solution, because reducing # uses of a value is general goodness (increases odds that "hasOneUse()" xforms will kick in for example).  

> Alternatively, it could look at uses of the select and try to simplify those
> first using InstructionSimplify (not sure if instcombine is allowed to
> simplify a different instruction to the one it is visiting), or check to see
> if some or all uses of the select would be simplified by InstructionSimplify,
> and not perform the transform if so.

Instead of turning this into a phase ordering issue, I'd rather increase the power of the folding logic to catch the general form.  In this case, instead of handling this in instsimplify, why not handle this in reassociate?

This is conceptually no different than (x & y & x) -> (x & y), it's just that in this case you have: (x & y & (x or -1)) which should fold to (x & y) just the same.

-Chris