This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] In foldSelectOpOp reuse existing selects if present
AbandonedPublic

Authored by john.brawn on Nov 13 2017, 8:24 AM.

Details

Summary

Currently foldSelectOpOp only optimises selects where the operands have only one use, in order to avoid a proliferation of select instructions. If we can reuse an existing select then we can relax this constraint.

This kind of pattern can happen when GVN PRE phi translation introduces a phi then later both of the phis become selects.

Diff Detail

Event Timeline

john.brawn created this revision.Nov 13 2017, 8:24 AM

Rebase, and ping now that D39958 has been committed.

I can see the transform that we want to make, but the way that this is coded seems wrong to me. We shouldn't have to search the block for existing operands to know if the transform is profitable.

What we should do instead is start the pattern match from a binop, so you're matching selects with a common condition operand and then binops with a common operand:

if (match(Op0, m_Select(m_Value(Cond), m_Value(A), m_Value(B))) &&
    match(Op1, m_Select(m_Specific(Cond), m_BinOp(C), m_BinOp(D))) &&
    C->getOpcode() == D->getOpcode() && 
    C->getOperand(1) == D->getOperand(1))

This would need to have the appropriate use-checks and commutations to work properly in all cases, but I think that's better than trying to go backwards from a select.

Alternatively, couldn't / shouldn't some other pass turn multiple selects with the same condition into compare/branch/phi?

I can see the transform that we want to make, but the way that this is coded seems wrong to me. We shouldn't have to search the block for existing operands to know if the transform is profitable.

What we should do instead is start the pattern match from a binop, so you're matching selects with a common condition operand and then binops with a common operand:

That would work for the test cases in the patch, but it's entirely possible to have the selects be used in unrelated instructions, e.g.

define i32 @example(i32 %x, i32 %y, i32* %ptr) {
  %add1 = add i32 %x, 1
  %add2 = add i32 %y, 1
  %cmp = icmp ugt i32 %x, %y
  %select1 = select i1 %cmp, i32 %x, i32 %y
  %select2 = select i1 %cmp, i32 %add1, i32 %add2
  %gep = getelementptr i32, i32* %ptr, i32 1
  store i32 %select1, i32* %ptr, align 4
  store i32 %select2, i32* %gep, align 4
  ret i32 %add1
}

Here we want to replace select2 with add i32 %select1, 1 but there's no user of select2 which also uses select1.

Alternatively, couldn't / shouldn't some other pass turn multiple selects with the same condition into compare/branch/phi?

As far as I know no (and it would have to be careful to agree with FoldTwoEntryPHINode in SimplifyCFG as to when it's a good idea), and I'm not sure how exactly it would help here? We'd be looking at phi instructions instead of select instructions, but that's it as far as I can tell.

john.brawn abandoned this revision.Mar 3 2020, 6:38 AM

Abandoning this old patch (the underlying problem was solved by https://reviews.llvm.org/rL348496 which made GVN PRE not introduce the problematic phis in the first place).

Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2020, 6:38 AM