CodeGenPrepare: Avoid and/or i1 in select conditions.

[MatzeB]

Summary

This transforms:
select((C0 & C1), a, b) -> select(C0, select(C1, a, b), b)
select((C0 | C1), a, b) -> select(C0, a, select(C1, a, b))

The result is better on most targets as C0 and C1 do not need to be
materialized into an integer register but can stay flags.

[hfinkel]

In my early tests the transformation was benficial on arm, aarch64, x86 but of course not on powerpc. Either the powerpc target should normalize into the other direction or we add another TargetTransformInfo flag that tells InstCombine which is the preferred form. I am not sure which to pick.

This is fine for PPC too. LLVM's PPC backend stores boolean values in CR bit registers, and on modern cores with isel, this transformation seems fairly neutral. Your first example goes from:

.L.test_select_and:
cmpw 0, 3, 6
cmpw 1, 3, 7
crandc 20, 4, 0
isel 3, 4, 5, 20
blr

to:

.L.test_select_andr:
cmpw 0, 3, 7
cmpw 7, 3, 6
isel 4, 4, 5, 0
isel 3, 5, 4, 28
blr

On a P7/P8, this seems pretty neutral (both the crandc and the isel are cracked). On the A2, you've increased the critical path length by 1 cycle (isel takes two cycles, but crandc only takes one). Nevertheless, I think that I can adjust for that during isel fairly easily.

The real question, as far as InstCombine goes, is does this make the most-useful canonical form? I'd tend to think that the answer is no, because the logical operators seem more likely to be amenable to further simplification than chains of selects. I could certainly be wrong, however. Also, not all cores have conditional moves (although many now do). Another option is to put this in DAGCombine (or CodeGenPrep), and there you might as well make it target customizable (I'd likely disable it for the PPC A2).

[MatzeB]

New Version: This expects the middleend to have selects normalized to selects with and/or conditions (see http://reviews.llvm.org/D7450). The Code to break it into a sequence of multiple selects is now in the CodeGenPrepare pass and relies on a TargetLowering hook to test whether the transformation is useful.

[MatzeB]

On a side note: Ahmed just mentioned a snipped from SelectionDAGBuilder to me that has pretty much the same logic I do for selects implemented for branches:

// If this is a series of conditions that are or'd or and'd together, emit

// this as a sequence of branches instead of setcc's with and/or operations.
// As long as jumps are not expensive, this should improve performance.
// For example, instead of something like:
//     cmp A, B
//     C = seteq
//     cmp D, E
//     F = setle
//     or C, F
//     jnz foo
// Emit:
//     cmp A, B
//     je foo
//     cmp D, E
//     jle foo
//

...

no idea why that is in SelectionDAGBuilder, it also doesn't seem strictly beneficial to all targets to me...

[hfinkel]

In D7399#119931, @MatzeB wrote:

On a side note: Ahmed just mentioned a snipped from SelectionDAGBuilder to me that has pretty much the same logic I do for selects implemented for branches:

// If this is a series of conditions that are or'd or and'd together, emit

// this as a sequence of branches instead of setcc's with and/or operations.
// As long as jumps are not expensive, this should improve performance.
// For example, instead of something like:
//     cmp A, B
//     C = seteq
//     cmp D, E
//     F = setle
//     or C, F
//     jnz foo
// Emit:
//     cmp A, B
//     je foo
//     cmp D, E
//     jle foo
//

...

no idea why that is in SelectionDAGBuilder, it also doesn't seem strictly beneficial to all targets to me...

It's not (and it was pointed out to me in a different thread a couple of months ago); which function does this again? I keep forgetting to fix this... (my current plan is to turn it off when TLI->hasMultipleConditionRegisters() is true, which is only the case on PPC AFAIK).

[MatzeB]

SelectionDAGBuilder::visitBr

[MatzeB]

ping

[hfinkel]

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

1195

I think that you want to explicitly add And to the worklist here (assuming that the builder has not constant-folded it).

if (Instruction *AndI = dyn_cast<Instruction>(And))
  Worklist.Add(AndI);

otherwise we might not actually revisit it until the next main outer instcombine iteration.

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
   if (isa<PHINode>(SI.getCondition()))
     // The true/false values have to be live in the PHI predecessor's blocks.
     if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
         CanSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
       if (Instruction *NV = FoldOpIntoPhi(SI))
         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)
+    // We choose this as normal form to enable folding on the And and shortening
+    // paths for the values (this helps GetUnderlyingObjects() for example).
+    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)) {
     SI.setOperand(0, BinaryOperator::getNotArgument(CondVal));
     SI.setOperand(1, FalseVal);
     SI.setOperand(2, TrueVal);
     return &SI;
   }

llvm/trunk/test/Transforms/InstCombine/select.ll

entry:
   call void @scribble_on_i128(i128* %x2)
   call void @scribble_on_i128(i128* %y)
   %tmp = load i8** %x1
   store i8* %tmp, i8** %y1
   %p = select i1 %flag, i128* %x2, i128* %y
   %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
+}