[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

202

Why is this being changed?

[aymanmus]

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

202

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

202

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.

202

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

static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {
   case Instruction::Sub:
   case Instruction::Mul:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor:
     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!");
   }
 }
 
 bool TruncInstCombine::buildTruncExpressionDag() {
   SmallVector<Value *, 8> Worklist;
   SmallVector<Instruction *, 8> Stack;
case Instruction::SExt:
       // trunc(ext(x)) -> trunc(x) if the source type is larger than the new
       // dest
       break;
     case Instruction::Add:
     case Instruction::Sub:
     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)
         Worklist.push_back(Operand);
       break;
     }
     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)
       // ...
       return false;
     }
   }
   return true;
while (!Worklist.empty()) {
     for (auto *Operand : Operands)
       if (auto *IOp = dyn_cast<Instruction>(Operand)) {
         // If we already calculated the minimum bit-width for this valid
         // bit-width, or for a smaller valid bit-width, then just keep the
         // answer we already calculated.
         unsigned IOpBitwidth = InstInfoMap.lookup(IOp).ValidBitWidth;
         if (IOpBitwidth >= ValidBitWidth)
           continue;
         InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;
         Worklist.push_back(IOp);
       }
   }
   unsigned MinBitWidth = InstInfoMap.lookup(cast<Instruction>(Src)).MinBitWidth;
   assert(MinBitWidth >= TruncBitWidth);
 
   if (MinBitWidth > TruncBitWidth) {
     // In this case reducing expression with vector type might generate a new
for (auto &Itr : InstInfoMap) { // Forward
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {
       Value *LHS = getReducedOperand(I->getOperand(0), SclTy);
       Value *RHS = getReducedOperand(I->getOperand(1), SclTy);
       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");
     }
 
     NodeInfo.NewValue = Res;
     if (auto *ResI = dyn_cast<Instruction>(Res))
       ResI->takeName(I);
   }

llvm/test/Transforms/AggressiveInstCombine/trunc_select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s
 ; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s
 
 target datalayout = "e-m:m-p1:64:64:64-p:32:32:32-n8:16:32"
 
 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
   %conv1 = sext i16 %b to i32
   %sel = select i1 %cond, i32 %conv0, i32 %conv1
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }
 
 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
   %conv1 = sext i8 %b to i32
   %sel = select i1 %cond, i32 %conv0, i32 %conv1
   %conv4 = trunc i32 %sel to i8
   ret i8 %conv4
 }
 
 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
   %conv1 = sext i8 %b to i32
   %sel = select i1 %cond, i32 %conv0, i32 %conv1
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }
 
 ;
 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
   %sel = select i1 %cond, i32 109, i32 %conv
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }
 
 ; 3080196 = 0x2f0004
 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
   %sel = select i1 %cond, i32 3080196, i32 %conv
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }
 
 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
   %sel = select i1 %cond, i32 109, i32 %conv
   %conv4 = trunc i32 %sel to i8
   ret i8 %conv4
 }
 
 ; 20228 = 0x4f02
 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
   %sel = select i1 %cond, i32 20228, i32 %conv
   %conv4 = trunc i32 %sel to i8
   ret i8 %conv4
 }
 
 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
   %sub = sub nsw i32 0, %conv
   %sel = select i1 %cond, i32 %sub, i32 %conv
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }
 
 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
   %sub = sub nsw i32 0, %conv
   %sel = select i1 %cond, i32 %sub, i32 %conv
   %conv4 = trunc i32 %sel to i16
   ret i16 %conv4
 }