[SCCP] Tune cast instruction handling for overdefined operand

[anton-afanasyev]

Summary

Extended value is known to be inside range smaller than full set.
Prevent SCCP to mark such value as overdefined.

Fixes PR52253

[fhahn]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

845

could that be handled by the code above, just with using the full range for OpRange if it is overdefined?

[anton-afanasyev]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

845

Ok, changed it this way, though getting a few more redundant computations.

[anton-afanasyev]

Address comment

[RKSimon]

I'm sorry, I'm not familiar with this code

[anton-afanasyev]

Ping.

[fhahn]

Thanks for the update! I think with the latest changes applied, I noticed another potential simplification.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

821

IIUC we need to check for range or overdefined here explicitly because we implicitly do not do anything for under or overdefined.

Could we instead add an early bail out on undeforunknown, only check for integer types here (and not constant range and overdefined) and drop the markOverdefined in the else of below?

[anton-afanasyev]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

821

Sure, thanks, dit it that way. Potentially this could be not NFC and improve handling of NotConstant operand, but SCCP doesn't use NotConstant state, so actually no change at all.

[anton-afanasyev]

Address comment

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Utils/SCCPSolver.cpp

821

Sure, thanks, dit it that way. Potentially this could be not NFC and improve handling of NotConstant operand, but SCCP doesn't use NotConstant state, so actually no change at all.

Yeah, NotConstant should not be used for integers at the very least, might be worth adding an assert here.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

 
 void SCCPInstVisitor::visitCastInst(CastInst &I) {
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (ValueState[&I].isOverdefined())
     return;
 
   ValueLatticeElement OpSt = getValueState(I.getOperand(0));
+  if (OpSt.isUnknownOrUndef())
+    return;
+
   if (Constant *OpC = getConstant(OpSt)) {
     // Fold the constant as we build.
     Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
     if (isa<UndefValue>(C))
       return;
     // Propagate constant value
     markConstant(&I, C);
-  } else if (OpSt.isConstantRange() && I.getDestTy()->isIntegerTy()) {
+  } else if (I.getDestTy()->isIntegerTy()) {
     auto &LV = getValueState(&I);
-    ConstantRange OpRange = OpSt.getConstantRange();
+    ConstantRange OpRange =
+        OpSt.isConstantRange()
+            ? OpSt.getConstantRange()
+            : ConstantRange::getFull(
+                  I.getOperand(0)->getType()->getScalarSizeInBits());
+
     Type *DestTy = I.getDestTy();
     // Vectors where all elements have the same known constant range are treated
     // as a single constant range in the lattice. When bitcasting such vectors,
     // there is a mis-match between the width of the lattice value (single
     // constant range) and the original operands (vector). Go to overdefined in
     // that case.
     if (I.getOpcode() == Instruction::BitCast &&
         I.getOperand(0)->getType()->isVectorTy() &&
         OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
       return (void)markOverdefined(&I);
 
     ConstantRange Res =
         OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
     mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
-  } else if (!OpSt.isUnknownOrUndef())
+  } else
     markOverdefined(&I);
 }
 
 void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
   // If this returns a struct, mark all elements over defined, we don't track
   // structs in structs.
   if (EVI.getType()->isStructTy())
     return (void)markOverdefined(&EVI);
 
   // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would

llvm/test/Transforms/PhaseOrdering/X86/pr52253.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -O3 -S < %s | FileCheck %s
 ; RUN: opt -instcombine -sccp -bdce -S < %s | FileCheck %s
-; RUN: opt -aggressive-instcombine -instcombine -sccp -bdce -S < %s | FileCheck %s --check-prefix=AIC_FIRST
+; RUN: opt -aggressive-instcombine -instcombine -sccp -bdce -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i1 @foo(i32 %t4, i32 %t10) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:    ret i1 false
 ;
-; AIC_FIRST-LABEL: @foo(
-; AIC_FIRST-NEXT:    ret i1 false
-;
   %t09 = shl i32 %t10, 24
   %t010 = ashr exact i32 %t09, 24
   %t011 = add nsw i32 %t010, 979
   %t11 = trunc i32 %t4 to i8
   %t12 = icmp eq i8 %t11, 0
   %t14 = zext i1 %t12 to i32
   %t15 = shl i32 %t4, %t14
   %t17 = and i32 %t15, 255
   %t18 = icmp eq i32 %t011, %t17
   ret i1 %t18
 }
 
 define i1 @bar(i32 %t4, i32 %t10) {
 ; CHECK-LABEL: @bar(
-; CHECK-NEXT:    [[T09:%.*]] = shl i32 [[T10:%.*]], 24
-; CHECK-NEXT:    [[T010:%.*]] = ashr exact i32 [[T09]], 24
-; CHECK-NEXT:    [[T011:%.*]] = add nsw i32 [[T010]], 979
-; CHECK-NEXT:    [[T11:%.*]] = trunc i32 [[T4:%.*]] to i8
-; CHECK-NEXT:    [[T12:%.*]] = icmp eq i8 [[T11]], 0
-; CHECK-NEXT:    [[T14:%.*]] = zext i1 [[T12]] to i8
-; CHECK-NEXT:    [[T15:%.*]] = shl i8 [[T11]], [[T14]]
-; CHECK-NEXT:    [[T17:%.*]] = zext i8 [[T15]] to i32
-; CHECK-NEXT:    [[T18:%.*]] = icmp eq i32 [[T011]], [[T17]]
-; CHECK-NEXT:    ret i1 [[T18]]
-;
-; AIC_FIRST-LABEL: @bar(
-; AIC_FIRST-NEXT:    [[T09:%.*]] = shl i32 [[T10:%.*]], 24
-; AIC_FIRST-NEXT:    [[T010:%.*]] = ashr exact i32 [[T09]], 24
-; AIC_FIRST-NEXT:    [[T011:%.*]] = add nsw i32 [[T010]], 979
-; AIC_FIRST-NEXT:    [[T11:%.*]] = trunc i32 [[T4:%.*]] to i8
-; AIC_FIRST-NEXT:    [[T12:%.*]] = icmp eq i8 [[T11]], 0
-; AIC_FIRST-NEXT:    [[T14:%.*]] = zext i1 [[T12]] to i8
-; AIC_FIRST-NEXT:    [[T15:%.*]] = shl i8 [[T11]], [[T14]]
-; AIC_FIRST-NEXT:    [[T17:%.*]] = zext i8 [[T15]] to i32
-; AIC_FIRST-NEXT:    [[T18:%.*]] = icmp eq i32 [[T011]], [[T17]]
-; AIC_FIRST-NEXT:    ret i1 [[T18]]
+; CHECK-NEXT:    ret i1 false
 ;
   %t09 = shl i32 %t10, 24
   %t010 = ashr exact i32 %t09, 24
   %t011 = add nsw i32 %t010, 979
   %t11 = trunc i32 %t4 to i8
   %t12 = icmp eq i8 %t11, 0
   %t14 = zext i1 %t12 to i8
   %t15 = shl i8 %t11, %t14
   %t17 = zext i8 %t15 to i32
   %t18 = icmp eq i32 %t011, %t17
   ret i1 %t18
 }
 
 define i1 @foobar(i32 %t4, i32 %t10) {
 ; CHECK-LABEL: @foobar(
 ; CHECK-NEXT:    ret i1 false
 ;
-; AIC_FIRST-LABEL: @foobar(
-; AIC_FIRST-NEXT:    [[T09:%.*]] = shl i32 [[T10:%.*]], 24
-; AIC_FIRST-NEXT:    [[T010:%.*]] = ashr exact i32 [[T09]], 24
-; AIC_FIRST-NEXT:    [[T011:%.*]] = add nsw i32 [[T010]], 979
-; AIC_FIRST-NEXT:    [[T11:%.*]] = trunc i32 [[T4:%.*]] to i8
-; AIC_FIRST-NEXT:    [[T12:%.*]] = icmp eq i8 [[T11]], 0
-; AIC_FIRST-NEXT:    [[T14:%.*]] = zext i1 [[T12]] to i8
-; AIC_FIRST-NEXT:    [[T15:%.*]] = shl i8 [[T11]], [[T14]]
-; AIC_FIRST-NEXT:    [[T17:%.*]] = zext i8 [[T15]] to i32
-; AIC_FIRST-NEXT:    [[T18:%.*]] = icmp eq i32 [[T011]], [[T17]]
-; AIC_FIRST-NEXT:    ret i1 [[T18]]
-;
   %t09 = shl i32 %t10, 24
   %t010 = ashr exact i32 %t09, 24
   %t011 = add nsw i32 %t010, 979
   %t11 = trunc i32 %t4 to i8
   %t12 = icmp eq i8 %t11, 0
   %t13 = zext i8 %t11 to i32
   %t14 = select i1 %t12, i32 1, i32 0
   %t15 = shl nuw nsw i32 %t13, %t14
   %t16 = trunc i32 %t15 to i8
   %t17 = zext i8 %t16 to i32
   %t18 = icmp eq i32 %t011, %t17
   ret i1 %t18
 }

llvm/test/Transforms/SCCP/ip-ranges-casts.ll

entry:
   %rem = srem <8 x i16> <i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2>, %vecinit7
   %0 = bitcast <8 x i16> %rem to i128
   %1 = trunc i128 %0 to i16
   ret i16 %1
 }
 
 define internal i64 @f.sext_to_zext(i32 %t) {
 ; CHECK-LABEL: @f.sext_to_zext(
-; CHECK-NEXT:    [[A:%.*]] = sext i32 [[T:%.*]] to i64
-; CHECK-NEXT:    ret i64 [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[T:%.*]] to i64
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %a = sext i32 %t to i64
   ret i64 %a
 }
 
 define i64 @caller.sext_to_zext(i32 %i) {
 ; CHECK-LABEL: @caller.sext_to_zext(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[I:%.*]], 9

llvm/test/Transforms/SCCP/overdefined-ext.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -sccp -S | FileCheck %s
 
 define i32 @zext_lshr(i1 %t0) {
 ; CHECK-LABEL: @zext_lshr(
 ; CHECK-NEXT:    [[T1:%.*]] = zext i1 [[T0:%.*]] to i32
-; CHECK-NEXT:    [[T2:%.*]] = lshr i32 [[T1]], 1
-; CHECK-NEXT:    ret i32 [[T2]]
+; CHECK-NEXT:    ret i32 0
 ;
   %t1 = zext i1 %t0 to i32
   %t2 = lshr i32 %t1, 1
   ret i32 %t2
 }
 
 define i1 @zext_icmp(i1 %t0) {
 ; CHECK-LABEL: @zext_icmp(
 ; CHECK-NEXT:    [[T1:%.*]] = zext i1 [[T0:%.*]] to i32
-; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 2
-; CHECK-NEXT:    ret i1 [[T2]]
+; CHECK-NEXT:    ret i1 false
 ;
   %t1 = zext i1 %t0 to i32
   %t2 = icmp eq i32 %t1, 2
   ret i1 %t2
 }
 
+; negative test. SCCP operates poorly with vector ranges
+
 define <2 x i1> @zext_vector(<2 x i1> %t0) {
 ; CHECK-LABEL: @zext_vector(
 ; CHECK-NEXT:    [[T1:%.*]] = zext <2 x i1> [[T0:%.*]] to <2 x i32>
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq <2 x i32> [[T1]], <i32 2, i32 2>
 ; CHECK-NEXT:    ret <2 x i1> [[T2]]
 ;
   %t1 = zext <2 x i1> %t0 to <2 x i32>
   %t2 = icmp eq <2 x i32> %t1, <i32 2, i32 2>
   ret <2 x i1> %t2
 }
 
+; negative test. SCCP operates poorly with vector ranges
+
 define <2 x i1> @zext_vector2(<2 x i1> %t0) {
 ; CHECK-LABEL: @zext_vector2(
 ; CHECK-NEXT:    [[T1:%.*]] = zext <2 x i1> [[T0:%.*]] to <2 x i32>
 ; CHECK-NEXT:    [[T2:%.*]] = add <2 x i32> [[T1]], <i32 2, i32 2>
 ; CHECK-NEXT:    [[T3:%.*]] = icmp eq <2 x i32> [[T1]], [[T2]]
 ; CHECK-NEXT:    ret <2 x i1> [[T3]]
 ;
   %t1 = zext <2 x i1> %t0 to <2 x i32>
   %t2 = add <2 x i32> %t1, <i32 2, i32 2>
   %t3 = icmp eq <2 x i32> %t1, %t2
   ret <2 x i1> %t3
 }
 
+; negative test: %t2 can be replaced by %t1, but SCCP operates by ranges only
+
 define i32 @sext_ashr(i1 %t0) {
 ; CHECK-LABEL: @sext_ashr(
 ; CHECK-NEXT:    [[T1:%.*]] = sext i1 [[T0:%.*]] to i32
 ; CHECK-NEXT:    [[T2:%.*]] = ashr i32 [[T1]], 1
 ; CHECK-NEXT:    ret i32 [[T2]]
 ;
   %t1 = sext i1 %t0 to i32
   %t2 = ashr i32 %t1, 1
   ret i32 %t2
 }
 
 define i1 @sext_icmp(i1 %t0) {
 ; CHECK-LABEL: @sext_icmp(
 ; CHECK-NEXT:    [[T1:%.*]] = sext i1 [[T0:%.*]] to i32
-; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 2
-; CHECK-NEXT:    ret i1 [[T2]]
+; CHECK-NEXT:    ret i1 false
 ;
   %t1 = sext i1 %t0 to i32
   %t2 = icmp eq i32 %t1, 2
   ret i1 %t2
 }
 
+; negative test. SCCP operates poorly with vector ranges
+
 define <2 x i1> @sext_vector(<2 x i1> %t0) {
 ; CHECK-LABEL: @sext_vector(
 ; CHECK-NEXT:    [[T1:%.*]] = sext <2 x i1> [[T0:%.*]] to <2 x i32>
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq <2 x i32> [[T1]], <i32 2, i32 2>
 ; CHECK-NEXT:    ret <2 x i1> [[T2]]
 ;
   %t1 = sext <2 x i1> %t0 to <2 x i32>
   %t2 = icmp eq <2 x i32> %t1, <i32 2, i32 2>
   ret <2 x i1> %t2
 }
 
+; negative test. SCCP operates poorly with vector ranges
+
 define <2 x i1> @sext_vector2(<2 x i1> %t0) {
 ; CHECK-LABEL: @sext_vector2(
 ; CHECK-NEXT:    [[T1:%.*]] = sext <2 x i1> [[T0:%.*]] to <2 x i32>
 ; CHECK-NEXT:    [[T2:%.*]] = add <2 x i32> [[T1]], <i32 2, i32 2>
 ; CHECK-NEXT:    [[T3:%.*]] = icmp eq <2 x i32> [[T1]], [[T2]]
 ; CHECK-NEXT:    ret <2 x i1> [[T3]]
 ;
   %t1 = sext <2 x i1> %t0 to <2 x i32>
   %t2 = add <2 x i32> %t1, <i32 2, i32 2>
   %t3 = icmp eq <2 x i32> %t1, %t2
   ret <2 x i1> %t3
 }

llvm/test/Transforms/SCCP/pr52253.ll

 ; CHECK-NEXT:    [[T09:%.*]] = shl i32 [[T10:%.*]], 24
 ; CHECK-NEXT:    [[T010:%.*]] = ashr exact i32 [[T09]], 24
 ; CHECK-NEXT:    [[T011:%.*]] = add nsw i32 [[T010]], 979
 ; CHECK-NEXT:    [[T11:%.*]] = trunc i32 [[T4:%.*]] to i8
 ; CHECK-NEXT:    [[T12:%.*]] = icmp eq i8 [[T11]], 0
 ; CHECK-NEXT:    [[T14:%.*]] = zext i1 [[T12]] to i8
 ; CHECK-NEXT:    [[T15:%.*]] = shl i8 [[T11]], [[T14]]
 ; CHECK-NEXT:    [[T17:%.*]] = zext i8 [[T15]] to i32
-; CHECK-NEXT:    [[T18:%.*]] = icmp eq i32 [[T011]], [[T17]]
-; CHECK-NEXT:    ret i1 [[T18]]
+; CHECK-NEXT:    ret i1 false
 ;
   %t09 = shl i32 %t10, 24
   %t010 = ashr exact i32 %t09, 24
   %t011 = add nsw i32 %t010, 979
   %t11 = trunc i32 %t4 to i8
   %t12 = icmp eq i8 %t11, 0
   %t14 = zext i1 %t12 to i8
   %t15 = shl i8 %t11, %t14

 ; CHECK-NEXT:    [[T011:%.*]] = add nsw i32 [[T010]], 979
 ; CHECK-NEXT:    [[T11:%.*]] = trunc i32 [[T4:%.*]] to i8
 ; CHECK-NEXT:    [[T12:%.*]] = icmp eq i8 [[T11]], 0
 ; CHECK-NEXT:    [[T13:%.*]] = zext i8 [[T11]] to i32
 ; CHECK-NEXT:    [[T14:%.*]] = select i1 [[T12]], i32 1, i32 0
 ; CHECK-NEXT:    [[T15:%.*]] = shl nuw nsw i32 [[T13]], [[T14]]
 ; CHECK-NEXT:    [[T16:%.*]] = trunc i32 [[T15]] to i8
 ; CHECK-NEXT:    [[T17:%.*]] = zext i8 [[T16]] to i32
-; CHECK-NEXT:    [[T18:%.*]] = icmp eq i32 [[T011]], [[T17]]
-; CHECK-NEXT:    ret i1 [[T18]]
+; CHECK-NEXT:    ret i1 false
 ;
   %t09 = shl i32 %t10, 24
   %t010 = ashr exact i32 %t09, 24
   %t011 = add nsw i32 %t010, 979
 
   %t11 = trunc i32 %t4 to i8
   %t12 = icmp eq i8 %t11, 0
   %t13 = zext i8 %t11 to i32
   %t14 = select i1 %t12, i32 1, i32 0
   %t15 = shl nuw nsw i32 %t13, %t14
   %t16 = trunc i32 %t15 to i8
   %t17 = zext i8 %t16 to i32
 
   %t18 = icmp eq i32 %t011, %t17
   ret i1 %t18
 }