[InstCombine] allow multi-use values in canEvaluate* if all uses are in 1 inst

[spatel]

Summary

This is the enhancement suggested in D42536 to fix a shortcoming in regular InstCombine's canEvaluate* functionality.
When we have multiple uses of a value, but they're all in one instruction, we can allow that expression to be narrowed or widened for the same cost as a single-use value.

AFAICT, this can only matter for multiply: sub/and/or/xor/select would be simplified away if the operands are the same value; add becomes shl; shifts with a variable shift amount aren't handled.

[aaboud]

LGTM.
Thanks for taking care of this.

[aaboud]

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

189 ↗

(On Diff #132469)

Sorry, I did not notice this before.
But should not we do the same check also for the "Select" and "PHI" below?
Could that be related to the infinite loop caused by this patch?

[spatel]

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

189 ↗

(On Diff #132469)

Yes, certainly for the select. I'm not sure about PHI though. A PHI with identical operands would be an invalid instruction?
'PHINode should have one entry for each predecessor of its parent basic block!'

[spatel]

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

189 ↗

(On Diff #132469)

I limited the multi-use evaluation to binops with rL324252 . That should disallow select and PHI, so hopefully closes the infinite looping potential. Still trying to come up with a test case.

lib/Transforms/InstCombine/InstCombineCasts.cpp

Value *InstCombiner::EvaluateInDifferentType(Value *V, Type *Ty,
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor:
   case Instruction::AShr:
   case Instruction::LShr:
   case Instruction::Shl:
   case Instruction::UDiv:
   case Instruction::URem: {
-    Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
-    Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
+    Value *LHS, *RHS;
+    if (I->getOperand(0) == I->getOperand(1)) {
+      // Don't create an unnecessary value if the operands are repeated.
+      LHS = RHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
+    } else {
+      LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
+      RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
+    }
     Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
     break;
   }
   case Instruction::Trunc:
   case Instruction::ZExt:
   case Instruction::SExt:
     // If the source type of the cast is the type we're trying for then we can
     // just return the source.  There's no need to insert it because it is not

 }
 
 /// Filter out values that we can not evaluate in the destination type for free.
 /// This is a helper for canEvaluate*.
 static bool canNotEvaluateInType(Value *V, Type *Ty) {
   assert(!isa<Constant>(V) && "Constant should already be handled.");
   if (!isa<Instruction>(V))
     return true;
-  // We can't extend or shrink something that has multiple uses: doing so would
-  // require duplicating the instruction in general, which isn't profitable.
+  // We can't extend or shrink something that has multiple uses -- unless those
+  // multiple uses are all in the same instruction -- doing so would require
+  // duplicating the instruction which isn't profitable.
   if (!V->hasOneUse())
+    if (any_of(V->users(), [&](User *U) { return U != V->user_back(); }))
       return true;
 
   return false;
 }
 
 /// Return true if we can evaluate the specified expression tree as type Ty
 /// instead of its larger type, and arrive with the same value.
 /// This is used by code that tries to eliminate truncates.
 ///

test/Transforms/InstCombine/cast-mul-select.ll

;
   %D = add i32 %A, %B
   %E = select i1 %cond, i32 %C, i32 %D
   %F = trunc i32 %E to i8
   ret i8 %F
 }
 
 define i32 @eval_trunc_multi_use_in_one_inst(i32 %x) {
 ; CHECK-LABEL: @eval_trunc_multi_use_in_one_inst(
-; CHECK-NEXT:    [[Z:%.*]] = zext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw i64 [[Z]], 15
-; CHECK-NEXT:    [[M:%.*]] = mul i64 [[A]], [[A]]
-; CHECK-NEXT:    [[T:%.*]] = trunc i64 [[M]] to i32
-; CHECK-NEXT:    ret i32 [[T]]
+; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], 15
+; CHECK-NEXT:    [[M:%.*]] = mul i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[M]]
 ;
   %z = zext i32 %x to i64
   %a = add nsw nuw i64 %z, 15
   %m = mul i64 %a, %a
   %t = trunc i64 %m to i32
   ret i32 %t
 }
 
 define i32 @eval_zext_multi_use_in_one_inst(i32 %x) {
 ; CHECK-LABEL: @eval_zext_multi_use_in_one_inst(
-; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[X:%.*]] to i16
-; CHECK-NEXT:    [[A:%.*]] = and i16 [[T]], 5
-; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i16 [[A]], [[A]]
-; CHECK-NEXT:    [[R:%.*]] = zext i16 [[M]] to i32
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[A:%.*]] = and i32 [[X:%.*]], 5
+; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[M]]
 ;
   %t = trunc i32 %x to i16
   %a = and i16 %t, 5
   %m = mul nuw nsw i16 %a, %a
   %r = zext i16 %m to i32
   ret i32 %r
 }
 
 define i32 @eval_sext_multi_use_in_one_inst(i32 %x) {
 ; CHECK-LABEL: @eval_sext_multi_use_in_one_inst(
-; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[X:%.*]] to i16
-; CHECK-NEXT:    [[A:%.*]] = and i16 [[T]], 14
-; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i16 [[A]], [[A]]
-; CHECK-NEXT:    [[O:%.*]] = or i16 [[M]], -32768
-; CHECK-NEXT:    [[R:%.*]] = sext i16 [[O]] to i32
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[A:%.*]] = and i32 [[X:%.*]], 14
+; CHECK-NEXT:    [[M:%.*]] = mul nuw nsw i32 [[A]], [[A]]
+; CHECK-NEXT:    [[O:%.*]] = or i32 [[M]], -32768
+; CHECK-NEXT:    ret i32 [[O]]
 ;
   %t = trunc i32 %x to i16
   %a = and i16 %t, 14
   %m = mul nuw nsw i16 %a, %a
   %o = or i16 %m, 32768
   %r = sext i16 %o to i32
   ret i32 %r
 }
 

test/Transforms/InstCombine/icmp-mul-zext.ll

 }
 
 ; https://bugs.llvm.org/show_bug.cgi?id=33765
 
 @glob = external global i16
 
 define void @PR33765(i8 %beth) {
 ; CHECK-LABEL: @PR33765(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[BETH:%.*]] to i32
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[BETH:%.*]] to i16
 ; CHECK-NEXT:    br i1 false, label [[IF_THEN9:%.*]], label [[IF_THEN9]]
 ; CHECK:       if.then9:
-; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV]], [[CONV]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i16 [[CONV]], [[CONV]]
 ; CHECK-NEXT:    [[TINKY:%.*]] = load i16, i16* @glob, align 2
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[MUL]] to i16
-; CHECK-NEXT:    [[CONV14:%.*]] = and i16 [[TINKY]], [[TMP1]]
+; CHECK-NEXT:    [[CONV14:%.*]] = and i16 [[TINKY]], [[MUL]]
 ; CHECK-NEXT:    store i16 [[CONV14]], i16* @glob, align 2
 ; CHECK-NEXT:    ret void
 ;
   %conv = zext i8 %beth to i32
   %mul = mul nuw nsw i32 %conv, %conv
   %conv3 = and i32 %mul, 255
   %tobool8 = icmp ne i32 %mul, %conv3
   br i1 %tobool8, label %if.then9, label %if.then9