[SCCP] Don't mark ranges from branch conditions as potentially undef

[nikic]

Summary

Now that transforms introducing branch on poison have been removed, we can stop marking ranges that have been derived from branch conditions as containing undef. The existing comment explains why this is legal. I've checked that alive2 is happy with SCCP tests after this change.

[fhahn]

LGTM, this should be fine after fixing the remaining (known) places that may introduce branches on undef.

I think it would probably be good to wait a few more days before landing this, so there's a bit of time between the change in ValueTracking & this one, in case any issues arise from the former.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       Value *OtherOp = Constraint->OtherOp;
 
       // Wait until OtherOp is resolved.
       if (getValueState(OtherOp).isUnknown()) {
         addAdditionalUser(OtherOp, &CB);
         return;
       }
 
-      // TODO: Actually filp MayIncludeUndef for the created range to false,
-      // once most places in the optimizer respect the branches on
-      // undef/poison are UB rule. The reason why the new range cannot be
-      // undef is as follows below:
-      // The new range is based on a branch condition. That guarantees that
-      // neither of the compare operands can be undef in the branch targets,
-      // unless we have conditions that are always true/false (e.g. icmp ule
-      // i32, %a, i32_max). For the latter overdefined/empty range will be
-      // inferred, but the branch will get folded accordingly anyways.
-      bool MayIncludeUndef = !isa<PredicateAssume>(PI);
-
       ValueLatticeElement CondVal = getValueState(OtherOp);
       ValueLatticeElement &IV = ValueState[&CB];
       if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
         auto ImposedCR =
             ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
 
         // Get the range imposed by the condition.
         if (CondVal.isConstantRange())
           ImposedCR = ConstantRange::makeAllowedICmpRegion(
               Pred, CondVal.getConstantRange());
 
         // Combine range info for the original value with the new range from the
         // condition.
         auto CopyOfCR = CopyOfVal.isConstantRange()
                             ? CopyOfVal.getConstantRange()
                             : ConstantRange::getFull(
                                   DL.getTypeSizeInBits(CopyOf->getType()));
         auto NewCR = ImposedCR.intersectWith(CopyOfCR);
         // If the existing information is != x, do not use the information from
         // a chained predicate, as the != x information is more likely to be
         // helpful in practice.
         if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
           NewCR = CopyOfCR;
 
+        // The new range is based on a branch condition. That guarantees that
+        // neither of the compare operands can be undef in the branch targets,
+        // unless we have conditions that are always true/false (e.g. icmp ule
+        // i32, %a, i32_max). For the latter overdefined/empty range will be
+        // inferred, but the branch will get folded accordingly anyways.
         addAdditionalUser(OtherOp, &CB);
-        mergeInValue(IV, &CB,
-                     ValueLatticeElement::getRange(NewCR, MayIncludeUndef));
+        mergeInValue(
+            IV, &CB,
+            ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));
         return;
       } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
         // For non-integer values or integer constant expressions, only
         // propagate equal constants.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
-      } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() &&
-                 !MayIncludeUndef) {
+      } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
         // Propagate inequalities.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB,
                      ValueLatticeElement::getNot(CondVal.getConstant()));
         return;
       }
 
       return (void)mergeInValue(IV, &CB, CopyOfVal);

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

false: ;%b in [0, 276)
   ; Conditions below cannot be simplified.
   %c.4 = icmp eq i32 %b, 21
   call void @use(i1 %c.4)
   %c.5 = icmp eq i32 %b, 275
   call void @use(i1 %c.5)
   ret void
 }
 
-; TODO: Use information %a != 0 in false branch.
 define void @f2_ptr(i8* %a, i8* %b) {
 ; CHECK-LABEL: @f2_ptr(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[BC:%.*]] = icmp eq i8* [[A:%.*]], null
 ; CHECK-NEXT:    br i1 [[BC]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i8* null, [[B:%.*]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i8* [[A]], null
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i8* [[A]], null
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i8* [[A]], [[B]]
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %bc = icmp eq i8* %a, null
   br i1 %bc, label %true, label %false
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=ipsccp -S %s -o -| FileCheck %s
 
 define i64 @test1(i32 %x) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[EXT_1:%.*]] = sext i32 [[X]] to i64
+; CHECK-NEXT:    [[EXT_1:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_1]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[X]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_2]]
 ;
   %c = icmp sgt i32 %x, 0
   br i1 %c, label %true, label %false
 
 true:
   %ext.1 = sext i32 %x to i64
   ret i64 %ext.1
 
 false:
   %ext.2 = sext i32 %x to i64
   ret i64 %ext.2
 }
 
 define i64 @test2(i32 %x) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[EXT_1:%.*]] = sext i32 [[X]] to i64
+; CHECK-NEXT:    [[EXT_1:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_1]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[X]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_2]]
 ;
   %c = icmp sge i32 %x, 0
   br i1 %c, label %true, label %false
 
exit:
   %p = phi i32 [ 0, %true.1 ], [ 1, %true.2], [ undef, %false ]
   %ext = sext i32 %p to i64
   ret i64 %ext
 }
 
 define i64 @test5(i32 %x) {
 ; CHECK-LABEL: @test5(
 ; 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
 }
 
 ; sext is constant folded before sext -> zext conversion.
 define i64 @test6(i32 %x) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    ret i64 10
 ;
   %ext = sext i32 10 to i64
   ret i64 %ext
 }
 
 ; sext that can be converted to zext feeds another sext.
 define i64 @test7(i16 %x) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:    [[P:%.*]] = and i16 [[X:%.*]], 15
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[P]] to i32
-; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[EXT_1:%.*]] = zext i16 [[P]] to i32
+; CHECK-NEXT:    [[EXT_2:%.*]] = sext i32 [[EXT_1]] to i64
 ; CHECK-NEXT:    ret i64 [[EXT_2]]
 ;
   %p = and i16 %x, 15
   %ext.1 = sext i16 %p to i32
   %ext.2 = sext i32 %ext.1 to i64
   ret i64 %ext.2
 }

llvm/test/Transforms/SCCP/replace-dereferenceable-ptr-with-undereferenceable.ll

 ; CHECK-LABEL: @eq_undereferenceable_cmp_simp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_0:%.*]] = icmp eq i32* [[P:%.*]], getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0)
 ; CHECK-NEXT:    br i1 [[CMP_0]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    store i32 2, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0), align 4
 ; CHECK-NEXT:    ret i1 true
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[CMP_2:%.*]] = icmp eq i32* [[P]], getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 1, i64 0)
-; CHECK-NEXT:    ret i1 [[CMP_2]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp.0 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   br i1 %cmp.0, label %if.then, label %if.end
 
 if.then:                                          ; preds = %entry
   store i32 2, i32* %p, align 4
   %cmp.1 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   ret i1 %cmp.1
 
 if.end:                                           ; preds = %if.then, %entry
   %cmp.2 = icmp eq i32* %p, getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1)
   ret i1 %cmp.2
 }