[SCCP] Propagate undef when visiting some instructions

[StephenFan]

Summary

If a value lattice is constantrange_including_undef, replaceSignInst to
unsigned Inst is invalid. But SCCPSolver didn't propagate undef when
visiting some instructions. This patch fixes this.

https://alive2.llvm.org/ce/z/85Ec-i
https://alive2.llvm.org/ce/z/jVZf67
https://alive2.llvm.org/ce/z/hZCw7k

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1246

Hm, this seems a bit inaccurate, in that something like zext i32 undef to i64 will still produce a value where the top bits are all zero, not undef. This would be more precisely modeled by treating undef as a full-set input. But then we would no longer model the case where undef doesn't matter as accurately...

[StephenFan]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1246

Yes. The way sccp handles undef is very conservative. For this patch, not only zext i32 under to i64, but also and i32 undef, -1 will be regarded as including_undef.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

if (Constant *OpC = getConstant(OpSt)) {
     // 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));
+    mergeInValue(LV, &I,
+                 ValueLatticeElement::getRange(
+                     Res, OpSt.isConstantRangeIncludingUndef()));
   } else
     markOverdefined(&I);
 }
 
 void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
                                                   const WithOverflowInst *WO,
                                                   unsigned Idx) {
   Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
   ValueLatticeElement L = getValueState(LHS);
   ValueLatticeElement R = getValueState(RHS);
   addAdditionalUser(LHS, &EVI);
   addAdditionalUser(RHS, &EVI);
   if (L.isUnknownOrUndef() || R.isUnknownOrUndef())
     return; // Wait to resolve.
 
   Type *Ty = LHS->getType();
   ConstantRange LR = getConstantRange(L, Ty);
   ConstantRange RR = getConstantRange(R, Ty);
   if (Idx == 0) {
     ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR);
-    mergeInValue(&EVI, ValueLatticeElement::getRange(Res));
+    mergeInValue(&EVI, ValueLatticeElement::getRange(
+                           Res, L.isConstantRangeIncludingUndef() ||
+                                    R.isConstantRangeIncludingUndef()));
   } else {
     assert(Idx == 1 && "Index can only be 0 or 1");
     ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
         WO->getBinaryOp(), RR, WO->getNoWrapKind());
     if (NWRegion.contains(LR))
       return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType()));
     markOverdefined(&EVI);
   }
void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
   // Only use ranges for binary operators on integers.
   if (!I.getType()->isIntegerTy())
     return markOverdefined(&I);
 
   // Try to simplify to a constant range.
   ConstantRange A = getConstantRange(V1State, I.getType());
   ConstantRange B = getConstantRange(V2State, I.getType());
   ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
-  mergeInValue(&I, ValueLatticeElement::getRange(R));
+  mergeInValue(&I, ValueLatticeElement::getRange(
+                       R, V1State.isConstantRangeIncludingUndef() ||
+                              V2State.isConstantRangeIncludingUndef()));
 
   // TODO: Currently we do not exploit special values that produce something
   // better than overdefined with an overdefined operand for vector or floating
   // point types, like and <4 x i32> overdefined, zeroinitializer.
 }
 
 // Handle ICmpInst instruction.
 void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       return (void)mergeInValue(IV, &CB, CopyOfVal);
     }
 
     if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
       // Compute result range for intrinsics supported by ConstantRange.
       // Do this even if we don't know a range for all operands, as we may
       // still know something about the result range, e.g. of abs(x).
       SmallVector<ConstantRange, 2> OpRanges;
+      bool MayIncludeUndef = false;
       for (Value *Op : II->args()) {
         const ValueLatticeElement &State = getValueState(Op);
+        if (State.isConstantRangeIncludingUndef())
+          MayIncludeUndef = true;
         OpRanges.push_back(getConstantRange(State, Op->getType()));
       }
 
       ConstantRange Result =
           ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
-      return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
+      return (void)mergeInValue(
+          II, ValueLatticeElement::getRange(Result, MayIncludeUndef));
     }
   }
 
   // The common case is that we aren't tracking the callee, either because we
   // are not doing interprocedural analysis or the callee is indirect, or is
   // external.  Handle these cases first.
   if (!F || F->isDeclaration())
     return handleCallOverdefined(CB);

llvm/test/Transforms/SCCP/ashr.ll

 f:
   %a = ashr i32 %x, %y
   br label %exit
 
 exit:
   %cond = phi i32 [ -42, %t ], [ %a, %f ]
   ret i32 %cond
 }
+
+define i32 @may_including_undef(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @may_including_undef(
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
+; CHECK:       true.1:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
+; CHECK:       true.2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 11, [[TRUE_1]] ], [ 13, [[TRUE_2]] ], [ undef, [[FALSE]] ]
+; CHECK-NEXT:    [[P1:%.*]] = add i32 [[P]], 1
+; CHECK-NEXT:    [[EXT:%.*]] = ashr i32 [[P1]], 1
+; CHECK-NEXT:    ret i32 [[EXT]]
+;
+  br i1 %c.1, label %true.1, label %false
+
+true.1:
+  br i1 %c.2, label %true.2, label %exit
+
+true.2:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %p = phi i32 [ 11, %true.1 ], [ 13, %true.2], [ undef, %false ]
+  %p1 = add i32 %p, 1
+  %ext = ashr i32 %p1, 1
+  ret i32 %ext
+}

llvm/test/Transforms/SCCP/ranges-sext.ll

exit:
   %p.fr = freeze i32 %p
   %ext = sext i32 %p.fr to i64
   ret i64 %ext
 }
 
 define i64 @test2(i32 %x) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[P:%.*]] = and i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[P]] to i64
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[P]] to i64
+; CHECK-NEXT:    ret i64 [[EXT]]
 ;
   %p = and i32 %x, 15
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 define i64 @test3(i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true.1:
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
 ; CHECK:       true.2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[TRUE_1]] ], [ 1, [[TRUE_2]] ], [ 3, [[FALSE]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[P]] to i64
-; CHECK-NEXT:    ret i64 [[TMP1]]
+; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[P]] to i64
+; CHECK-NEXT:    ret i64 [[EXT]]
 ;
   br i1 %c.1, label %true.1, label %false
 
 true.1:
   br i1 %c.2, label %true.2, label %exit
 
 true.2:
   br label %exit
 
 false:
   br label %exit
 
 exit:
   %p = phi i32 [ 0, %true.1 ], [ 1, %true.2], [ 3, %false ]
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
+
+define i64 @binary_may_including_undef(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @binary_may_including_undef(
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
+; CHECK:       true.1:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
+; CHECK:       true.2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[TRUE_1]] ], [ 2, [[TRUE_2]] ], [ undef, [[FALSE]] ]
+; CHECK-NEXT:    [[P1:%.*]] = add i32 [[P]], 1
+; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[P1]] to i64
+; CHECK-NEXT:    ret i64 [[EXT]]
+;
+  br i1 %c.1, label %true.1, label %false
+
+true.1:
+  br i1 %c.2, label %true.2, label %exit
+
+true.2:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %p = phi i32 [ 1, %true.1 ], [ 2, %true.2], [ undef, %false ]
+  %p1 = add i32 %p, 1
+  %ext = sext i32 %p1 to i64
+  ret i64 %ext
+}
+
+declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)
+define i64 @with_overflow_may_including_undef(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @with_overflow_may_including_undef(
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
+; CHECK:       true.1:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
+; CHECK:       true.2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[TRUE_1]] ], [ 2, [[TRUE_2]] ], [ undef, [[FALSE]] ]
+; CHECK-NEXT:    [[P1:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[P]], i32 1)
+; CHECK-NEXT:    [[P2:%.*]] = extractvalue { i32, i1 } [[P1]], 0
+; CHECK-NEXT:    [[EXT:%.*]] = sext i32 [[P2]] to i64
+; CHECK-NEXT:    ret i64 [[EXT]]
+;
+  br i1 %c.1, label %true.1, label %false
+
+true.1:
+  br i1 %c.2, label %true.2, label %exit
+
+true.2:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %p = phi i32 [ 1, %true.1 ], [ 2, %true.2], [ undef, %false ]
+  %p1 = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %p, i32 1)
+  %p2 = extractvalue { i32, i1 } %p1, 0
+  %ext = sext i32 %p2 to i64
+  ret i64 %ext
+}
+
+declare i8 @llvm.umax.i8(i8, i8)
+define i16 @intrinsic_may_including_undef(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @intrinsic_may_including_undef(
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[TRUE_1:%.*]], label [[FALSE:%.*]]
+; CHECK:       true.1:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[TRUE_2:%.*]], label [[EXIT:%.*]]
+; CHECK:       true.2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi i8 [ 1, [[TRUE_1]] ], [ 102, [[TRUE_2]] ], [ undef, [[FALSE]] ]
+; CHECK-NEXT:    [[P1:%.*]] = call i8 @llvm.umax.i8(i8 [[P]], i8 100)
+; CHECK-NEXT:    [[EXT:%.*]] = sext i8 [[P1]] to i16
+; CHECK-NEXT:    ret i16 [[EXT]]
+;
+  br i1 %c.1, label %true.1, label %false
+
+true.1:
+  br i1 %c.2, label %true.2, label %exit
+
+true.2:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %p = phi i8 [ 1, %true.1 ], [ 102, %true.2], [ undef, %false ]
+  %p1 = call i8 @llvm.umax.i8(i8 %p, i8 100)
+  %ext = sext i8 %p1 to i16
+  ret i16 %ext
+}