[InstCombine] In foldSelectOpOp reuse existing selects if present

[john.brawn]

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.

[john.brawn]

Rebase, and ping now that D39958 has been committed.

[spatel]

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?

[john.brawn]

In D39960#987169, @spatel wrote:

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]

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).

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (TI->getNumOperands() == 1 && TI->isCast()) {
     // Fold this by inserting a select from the input values.
     Value *NewSI =
         Builder.CreateSelect(SI.getCondition(), TI->getOperand(0),
                              FI->getOperand(0), SI.getName() + ".v", &SI);
     return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,
                             TI->getType());
   }
 
-  // Only handle binary operators (including two-operand getelementptr) with
-  // one-use here. As with the cast case above, it may be possible to relax the
-  // one-use constraint, but that needs be examined carefully since it may not
-  // reduce the total number of instructions.
+  // Only handle binary operators (including two-operand getelementptr) here.
   if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||
-      (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) ||
-      !TI->hasOneUse() || !FI->hasOneUse())
+      (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)))
     return nullptr;
 
   // Figure out if the operations have any operands in common.
   Value *MatchOp, *OtherOpT, *OtherOpF;
   bool MatchIsOpZero;
   if (TI->getOperand(0) == FI->getOperand(0)) {
     MatchOp  = TI->getOperand(0);
     OtherOpT = TI->getOperand(1);
if (TI->getOperand(0) == FI->getOperand(0)) {
     MatchOp  = TI->getOperand(1);
     OtherOpT = TI->getOperand(0);
     OtherOpF = FI->getOperand(1);
     MatchIsOpZero = true;
   } else {
     return nullptr;
   }
 
-  // If we reach here, they do have operations in common.
-  Value *NewSI = Builder.CreateSelect(SI.getCondition(), OtherOpT, OtherOpF,
-                                      SI.getName() + ".v", &SI);
+  // If we reach here, they do have operations in common. First check if there
+  // already exists a select of the differing operands.
+  Value *NewSI = nullptr;
+  for (Instruction &I : *SI.getParent()) {
+    if (isa<SelectInst>(I) && I.getOperand(0) == SI.getOperand(0) &&
+        I.getOperand(1) == OtherOpT && I.getOperand(2) == OtherOpF) {
+      // We can safely move I before SI as its operands are operands (of
+      // operands of) SI, so are already defined at this point.
+      I.moveBefore(&SI);
+      NewSI = &I;
+      break;
+    }
+  }
+
+  // If there isn't already a select then create one if the select operands have
+  // only one use. As with the cast case above, it may be possible to relax the
+  // one-use constraint, but that needs be examined carefully since it may not
+  // reduce the total number of instructions.
+  if (!NewSI) {
+    if (!TI->hasOneUse() || !FI->hasOneUse())
+      return nullptr;
+    NewSI = Builder.CreateSelect(SI.getCondition(), OtherOpT, OtherOpF,
+  }
   Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
   Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI))
     return BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
   else if (GetElementPtrInst *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
     GetElementPtrInst *FGEP = dyn_cast<GetElementPtrInst>(FI);
     Type *ElementType = TGEP->getResultElementType();
     return TGEP->isInBounds() && FGEP->isInBounds()

test/Transforms/InstCombine/select-reuse.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Check that we reuse a select instead of adding a new one
+; CHECK-LABEL: @test1
+; CHECK: [[SEL:%.*]] = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NOT: select i1 %cmp, i32 %x, i32 %y
+; CHECK: add i32 [[SEL]], 1
+define i32 @test1(i32 %x, i32 %y) {
+  %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
+  %mul = mul i32 %select1, %select2
+  ret i32 %mul
+}
+
+; Check that we can optimise a select whose operands are used more than once by
+; reusing an existing select
+; CHECK-LABEL: @test2a
+; CHECK: [[SEL:%.*]] = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NOT: select i1 %cmp, i32 %add1, i32 %add2
+; CHECK: add i32 [[SEL]], 1
+define i32 @test2a(i32 %x, i32 %y) {
+  %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
+  %mul1 = mul i32 %select1, %select2
+  %mul2 = mul i32 %mul1, %add1
+  ret i32 %mul2
+}
+
+; CHECK-LABEL: @test2b
+; CHECK: [[SEL:%.*]] = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NOT: select i1 %cmp, i32 %add1, i32 %add2
+; CHECK: add i32 [[SEL]], 1
+define i32 @test2b(i32 %x, i32 %y) {
+  %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
+  %mul1 = mul i32 %select1, %select2
+  %mul2 = mul i32 %mul1, %add2
+  ret i32 %mul2
+}
+
+; CHECK-LABEL: @test2c
+; CHECK: [[SEL:%.*]] = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NOT: select i1 %cmp, i32 %add1, i32 %add2
+; CHECK: add i32 [[SEL]], 1
+define i32 @test2c(i32 %x, i32 %y) {
+  %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
+  %mul1 = mul i32 %select1, %select2
+  %mul2 = mul i32 %mul1, %add1
+  %mul3 = mul i32 %mul2, %add2
+  ret i32 %mul3
+}