InstCombine: Combine select sequences into a single select

[MatzeB]

Summary

Normalize
select(C0, select(C1, a, b), b) -> select((C0 & C1), a, b)
select(C0, a, select(C1, a, b)) -> select((C0 | C1), a, b)

This form may enabled further combines on the And and Or part
conditions. For most targets the select sequence is actually preferable
though, a followup patch will change DAGCombine to go back to the previous
form.

[hfinkel]

LGTM.

lib/Transforms/InstCombine/InstCombineSelect.cpp

1190

The other reason this helps, which I think is worth mentioning, is that GetUnderlyingObjects (which is used both at the IR level proper in several places, and also used on MMOs by the instruction scheduler) only looks back through a fixed number of PHIs and selects. Thus, reducing the select depth makes several things more powerful "for free".

[MatzeB]

Committed in r228409

lib/Transforms/InstCombine/InstCombineSelect.cpp

         return NV;
 
   if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
+    // select(C, select(C, a, b), c) -> select(C, a, c)
     if (TrueSI->getCondition() == CondVal) {
       if (SI.getTrueValue() == TrueSI->getTrueValue())
         return nullptr;
       SI.setOperand(1, TrueSI->getTrueValue());
       return &SI;
     }
+    // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
+    // Note: This form potentially enables more folding to happen on the And
+    // DAGCombine will probably go back to the select sequencing form later.
+    if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
+      Value *And = Builder->CreateAnd(CondVal, TrueSI->getCondition());
+      SI.setOperand(0, And);
+      SI.setOperand(1, TrueSI->getTrueValue());
+      return &SI;
+    }
   }
   if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
+    // select(C, a, select(C, b, c)) -> select(C, a, c)
     if (FalseSI->getCondition() == CondVal) {
       if (SI.getFalseValue() == FalseSI->getFalseValue())
         return nullptr;
       SI.setOperand(2, FalseSI->getFalseValue());
       return &SI;
     }
+    // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
+    if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
+      Value *Or = Builder->CreateOr(CondVal, FalseSI->getCondition());
+      SI.setOperand(0, Or);
+      SI.setOperand(2, FalseSI->getFalseValue());
+      return &SI;
+    }
   }
 
   if (BinaryOperator::isNot(CondVal)) {

test/Transforms/InstCombine/select.ll

   %v = load i128* %p
   ret i128 %v
 }
+
+define i32 @test_select_select0(i32 %a, i32 %r0, i32 %r1, i32 %v1, i32 %v2) {
+  ; CHECK-LABEL: @test_select_select0(
+  ; CHECK: %[[C0:.*]] = icmp sge i32 %a, %v1
+  ; CHECK-NEXT: %[[C1:.*]] = icmp slt i32 %a, %v2
+  ; CHECK-NEXT: %[[C:.*]] = and i1 %[[C1]], %[[C0]]
+  ; CHECK-NEXT: %[[SEL:.*]] = select i1 %[[C]], i32 %r0, i32 %r1
+  ; CHECK-NEXT: ret i32 %[[SEL]]
+  %c0 = icmp sge i32 %a, %v1
+  %s0 = select i1 %c0, i32 %r0, i32 %r1
+  %c1 = icmp slt i32 %a, %v2
+  %s1 = select i1 %c1, i32 %s0, i32 %r1
+  ret i32 %s1
+}
+
+define i32 @test_select_select1(i32 %a, i32 %r0, i32 %r1, i32 %v1, i32 %v2) {
+  ; CHECK-LABEL: @test_select_select1(
+  ; CHECK: %[[C0:.*]] = icmp sge i32 %a, %v1
+  ; CHECK-NEXT: %[[C1:.*]] = icmp slt i32 %a, %v2
+  ; CHECK-NEXT: %[[C:.*]] = or i1 %[[C1]], %[[C0]]
+  ; CHECK-NEXT: %[[SEL:.*]] = select i1 %[[C]], i32 %r0, i32 %r1
+  ; CHECK-NEXT: ret i32 %[[SEL]]
+  %c0 = icmp sge i32 %a, %v1
+  %s0 = select i1 %c0, i32 %r0, i32 %r1
+  %c1 = icmp slt i32 %a, %v2
+  %s1 = select i1 %c1, i32 %r0, i32 %s0
+  ret i32 %s1
+}