[AggressiveInstCombine] Add support for select instruction.

[aymanmus]

Summary

Add support for select instructions in the sequences that may be optimized in the AggressiveInstCombine pass.

[lebedev.ri]

This is certainly missing tests

[aymanmus]

Somehow the test wasn't included with the differential text file.
Adding now.

[spatel]

Verify that the translation is correct, but I don't think this patch is safe:

define i16 @cmp_select_sext_const(i8 %a) {
  %conv = sext i8 %a to i32
  %cmp = icmp slt i32 %conv, 32768
  %cond = select i1 %cmp, i32 32768, i32 %conv
  %conv4 = trunc i32 %cond to i16
  ret i16 %conv4
}

$ opt -aggressive-instcombine agg.ll -S
define i16 @cmp_select_sext_const(i8 %a) {
  %conv = sext i8 %a to i16
  %cmp = icmp slt i16 %conv, -32768
  %cond = select i1 %cmp, i16 -32768, i16 %conv
  ret i16 %cond
}

https://rise4fun.com/Alive/JCo

[aymanmus]

Fix @spatel's test case. Thanks for the review.
Involve constants in cmp operations in the MinBitWidth calculations.

[nikic]

Is it possible to split this into a patch that adds just the select handling, and another that extends the icmp support? It seems like the select part should be testable independently, as long as you don't derive the select condition from the select operands.

[aymanmus]

Following @nikic's comment:
I agree, the patch is missing some select exclusive tests.
Adding such test cases.
IMHO, there is no added value to splitting to 2 patches, the select changed are too obvious, and the compare is strongly related to the select changes.

[nikic]

In D72837#1840886, @aymanmus wrote:

IMHO, there is no added value to splitting to 2 patches, the select changed are too obvious, and the compare is strongly related to the select changes.

That's kind of the point: The select change is obvious and can land right away, the icmp part is trickier.

I'm not really familiar with this code, but coupling the icmp and the select handling seems like a bit of a hack: The transform is also possible if the select condition is unrelated to the trunc chain, and the transform is also possible if there is an icmp dependent on the trunc chain but not used in a select condition. I think the more principled approach would be to extend the code in https://github.com/llvm/llvm-project/blob/0e0c65264aeb6f66b6f711884c55cdbf66d975f6/llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp#L241-L256 to collect the extra use icmp.

[spatel]

In D72837#1841046, @nikic wrote:

In D72837#1840886, @aymanmus wrote:

IMHO, there is no added value to splitting to 2 patches, the select changed are too obvious, and the compare is strongly related to the select changes.

That's kind of the point: The select change is obvious and can land right away, the icmp part is trickier.

+1. Minimal patches are easier to review/debug, and we've already shown that this patch has tricky edge cases (and I don't know this code very well either). Also, please push the test file with baseline CHECKs as a preliminary commit.

[aymanmus]

Removed all cmp instruction handling to get a pure SELECT patch support.

[lebedev.ri]

Please upload all patches with full context (-U99999)

[aymanmus]

Adding full context to patch.

[lebedev.ri]

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

203

Why is this being changed?

[aymanmus]

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

203

The max operation is not needed here.
If we reach this point of the code, then ValidBitWidth MUST be bigger than IOpBitwidth (because other wise we'll hit the "continue" at line 202.

[lebedev.ri]

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

203

Can you submit that as a separate change then please?

[nikic]

LGTM

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

59

Style nit: Omit {} if not necessary.

203

This change looks fine, but please commit it independently as NFC.

[aymanmus]

Extract the std::max omission to a separate patch as requested (patch D74476)

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

     Ops.push_back(I->getOperand(0));
     Ops.push_back(I->getOperand(1));
     break;
+  case Instruction::Select: {
+    Ops.push_back(I->getOperand(1));
+    Ops.push_back(I->getOperand(2));
+    break;
+  }
   default:
     llvm_unreachable("Unreachable!");
   }

     case Instruction::Mul:
     case Instruction::And:
     case Instruction::Or:
-    case Instruction::Xor: {
+    case Instruction::Xor:
+    case Instruction::Select: {
       SmallVector<Value *, 2> Operands;
       getRelevantOperands(I, Operands);
       for (Value *Operand : Operands)

     }
     default:
       // TODO: Can handle more cases here:
-      // 1. select, shufflevector, extractelement, insertelement
+      // 1. shufflevector, extractelement, insertelement
       // 2. udiv, urem
       // 3. shl, lshr, ashr
       // 4. phi node(and loop handling)

         unsigned IOpBitwidth = InstInfoMap.lookup(IOp).ValidBitWidth;
         if (IOpBitwidth >= ValidBitWidth)
           continue;
-        InstInfoMap[IOp].ValidBitWidth = std::max(ValidBitWidth, IOpBitwidth);
+        InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;
         Worklist.push_back(IOp);
       }
   }

       Res = Builder.CreateBinOp((Instruction::BinaryOps)Opc, LHS, RHS);
       break;
     }
+    case Instruction::Select: {
+      Value *Op0 = I->getOperand(0);
+      Value *LHS = getReducedOperand(I->getOperand(1), SclTy);
+      Value *RHS = getReducedOperand(I->getOperand(2), SclTy);
+      Res = Builder.CreateSelect(Op0, LHS, RHS);
+      break;
+    }
     default:
       llvm_unreachable("Unhandled instruction");
     }

llvm/test/Transforms/AggressiveInstCombine/trunc_select.ll

 define dso_local i16 @select_i16(i16 %a, i16 %b, i1 %cond) {
 ; CHECK-LABEL: @select_i16(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV0:%.*]] = sext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[CONV1:%.*]] = sext i16 [[B:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 [[CONV0]], i32 [[CONV1]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 [[A:%.*]], i16 [[B:%.*]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv0 = sext i16 %a to i32

 define dso_local i8 @select_i8(i8 %a, i8 %b, i1 %cond) {
 ; CHECK-LABEL: @select_i8(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV0:%.*]] = sext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[CONV1:%.*]] = sext i8 [[B:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 [[CONV0]], i32 [[CONV1]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i8
-; CHECK-NEXT:    ret i8 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i8 [[A:%.*]], i8 [[B:%.*]]
+; CHECK-NEXT:    ret i8 [[SEL]]
 ;
 entry:
   %conv0 = sext i8 %a to i32

 define dso_local i16 @select_i8Ops_trunc_i16(i8 %a, i8 %b, i1 %cond) {
 ; CHECK-LABEL: @select_i8Ops_trunc_i16(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV0:%.*]] = sext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[CONV1:%.*]] = sext i8 [[B:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 [[CONV0]], i32 [[CONV1]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[CONV0:%.*]] = sext i8 [[A:%.*]] to i16
+; CHECK-NEXT:    [[CONV1:%.*]] = sext i8 [[B:%.*]] to i16
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 [[CONV0]], i16 [[CONV1]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv0 = sext i8 %a to i32

 define dso_local i16 @select_i16_const(i16 %a, i1 %cond) {
 ; CHECK-LABEL: @select_i16_const(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 109, i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 109, i16 [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv = sext i16 %a to i32

 define dso_local i16 @select_i16_bigConst(i16 %a, i1 %cond) {
 ; CHECK-LABEL: @select_i16_bigConst(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 3080196, i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 4, i16 [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv = sext i16 %a to i32

 define dso_local i8 @select_i8_const(i8 %a, i1 %cond) {
 ; CHECK-LABEL: @select_i8_const(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 109, i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i8
-; CHECK-NEXT:    ret i8 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i8 109, i8 [[A:%.*]]
+; CHECK-NEXT:    ret i8 [[SEL]]
 ;
 entry:
   %conv = sext i8 %a to i32

 define dso_local i8 @select_i8_bigConst(i8 %a, i1 %cond) {
 ; CHECK-LABEL: @select_i8_bigConst(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 20228, i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i8
-; CHECK-NEXT:    ret i8 [[CONV4]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i8 4, i8 [[A:%.*]]
+; CHECK-NEXT:    ret i8 [[SEL]]
 ;
 entry:
   %conv = sext i8 %a to i32

 define dso_local i16 @select_sext(i8 %a, i1 %cond) {
 ; CHECK-LABEL: @select_sext(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[CONV]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 [[SUB]], i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[CONV:%.*]] = sext i8 [[A:%.*]] to i16
+; CHECK-NEXT:    [[SUB:%.*]] = sub i16 0, [[CONV]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 [[SUB]], i16 [[CONV]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv = sext i8 %a to i32

 define dso_local i16 @select_zext(i8 %a, i1 %cond) {
 ; CHECK-LABEL: @select_zext(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[A:%.*]] to i32
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[CONV]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 [[SUB]], i32 [[CONV]]
-; CHECK-NEXT:    [[CONV4:%.*]] = trunc i32 [[SEL]] to i16
-; CHECK-NEXT:    ret i16 [[CONV4]]
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[A:%.*]] to i16
+; CHECK-NEXT:    [[SUB:%.*]] = sub i16 0, [[CONV]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i16 [[SUB]], i16 [[CONV]]
+; CHECK-NEXT:    ret i16 [[SEL]]
 ;
 entry:
   %conv = zext i8 %a to i32