[ValueLattice] Merging unknown with empty CR is unknown.

[fhahn]

Summary

Currently an unknown/undef value is marked as overdefined when merged
with an empty range. An empty range can occur in unreachable/dead code.
When merging the new unknown state (= no value known yet) with an empty
range, there still isn't any information about the value yet and we can
stay in unknown.

This gives a few nice improvements on the number of instructions removed
by IPSCCP:
Same hash: 170 (filtered out)
Remaining: 67
Metric: sccp.IPNumInstRemoved

Program base patch diff
test-suite...rks/FreeBench/mason/mason.test 3.00 6.00 100.0%
test-suite...nchmarks/McCat/18-imp/imp.test 3.00 5.00 66.7%
test-suite...C/CFP2000/179.art/179.art.test 2.00 3.00 50.0%
test-suite...ijndael/security-rijndael.test 2.00 3.00 50.0%
test-suite...ks/Prolangs-C/agrep/agrep.test 40.00 58.00 45.0%
test-suite...ce/Applications/Burg/burg.test 26.00 37.00 42.3%
test-suite...cCat/03-testtrie/testtrie.test 3.00 4.00 33.3%
test-suite...Source/Benchmarks/sim/sim.test 29.00 36.00 24.1%
test-suite.../Applications/spiff/spiff.test 9.00 11.00 22.2%
test-suite...s/FreeBench/neural/neural.test 5.00 6.00 20.0%
test-suite...pplications/treecc/treecc.test 66.00 79.00 19.7%
test-suite...langs-C/football/football.test 85.00 101.00 18.8%
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 90.00 105.00 16.7%
test-suite...oxyApps-C++/miniFE/miniFE.test 37.00 43.00 16.2%
test-suite...rks/FreeBench/pifft/pifft.test 26.00 30.00 15.4%
test-suite...lications/sqlite3/sqlite3.test 481.00 548.00 13.9%
test-suite...marks/7zip/7zip-benchmark.test 4875.00 5522.00 13.3%
test-suite.../CINT2000/176.gcc/176.gcc.test 1117.00 1197.00 7.2%
test-suite...0.perlbench/400.perlbench.test 1618.00 1732.00 7.0%

[fhahn]

Rebased

[nikic]

llvm/include/llvm/Analysis/ValueLattice.h

361–362

Can't we do this for the isUndef() case as well, i.e. return false here unconditionally?

[efriedma]

markConstantRange with an empty range should be equivalent to markUnknown (i.e. it shouldn't do anything at all).

[efriedma]

(And if MayIncludeUndef is set, it's equivalent to markUndef().)

[fhahn]

update getRange() to return either unknown or undef for empty ranges, depending on MayIncludeUndef. In markConstantRange, assert that only non-empty ranges are passed. I'll update the description accordinly

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

361–362

Can't we do this for the isUndef() case as well, i.e. return false here unconditionally?

I can't think of a reason now why not, but it seems like this has been there for a long time. Not sure if that is/was a LVI specific assumption in the original code. I've adjusted the code and now empty ranges should never reach markConstantRange.

(@efriedma I'll include the responses to your comments inline here, as they seem to fit with the context here)

markConstantRange with an empty range should be equivalent to markUnknown (i.e. it shouldn't do anything at all).

Eli, do you by any chance remember why the restriction was there in the first place? I agree, it seems like we should just treat empty set as if merging with unknown. I think the better fix would be to not create constantrange lattice values in the first place with empty ranges (needs a fix in getRange()).

(And if MayIncludeUndef is set, it's equivalent to markUndef().)

I tried to come up with cases where markUndef would be required for empty ranges but I couldn't, as the empty ranges should only occur in dead blocks. But I guess it is better to start out with being a bit more conservative.

[nikic]

llvm/include/llvm/Analysis/ValueLattice.h

361–362

One thing to keep in mind here is that empty range can occur not only if the block is dead, but also if immediate UB is triggered (I believe you'll get an empty set from udiv by zero) and if an instruction always returns poison (e.g. due to nowrap flags -- SCCP is probably not wired up to this part, but LVI is). I don't think this changes anything about the conclusion here though.

If the behavior here is changed, this comment in LVI should also be updated: https://github.com/llvm/llvm-project/blob/45526d29a5b2cf126b83ada3991921970007d16f/llvm/lib/Analysis/LazyValueInfo.cpp#L125-L127

[fhahn]

If the behavior here is changed, this comment in LVI should also be updated: https://github.com/llvm/llvm-project/blob/45526d29a5b2cf126b83ada3991921970007d16f/llvm/lib/Analysis/LazyValueInfo.cpp#L125-L127

Thanks, removed the TODO and updated the note.

[efriedma]

LGTM

llvm/include/llvm/Analysis/ValueLattice.h

361–362

Eli, do you by any chance remember why the restriction was there in the first place?

You mean, why we sent empty ranges to overdefined? No memory of this. Tried to dig a bit into blame, and I think it goes back to https://reviews.llvm.org/rL110388 .

llvm/include/llvm/Analysis/ValueLattice.h

static ValueLatticeElement getNot(Constant *C) {
     Res.markNotConstant(C);
     return Res;
   }
   static ValueLatticeElement getRange(ConstantRange CR,
                                       bool MayIncludeUndef = false) {
     if (CR.isFullSet())
       return getOverdefined();
 
+    if (CR.isEmptySet()) {
+      ValueLatticeElement Res;
+      if (MayIncludeUndef)
+        Res.markUndef();
+      return Res;
+    }
+
     ValueLatticeElement Res;
     Res.markConstantRange(std::move(CR),
                           MergeOptions().setMayIncludeUndef(MayIncludeUndef));
     return Res;
   }
   static ValueLatticeElement getOverdefined() {
     ValueLatticeElement Res;
     Res.markOverdefined();
public:
   /// Mark the object as constant range with \p NewR. If the object is already a
   /// constant range, nothing changes if the existing range is equal to \p
   /// NewR and the tag. Otherwise \p NewR must be a superset of the existing
   /// range or the object must be undef. The tag is set to
   /// constant_range_including_undef if either the existing value or the new
   /// range may include undef.
   bool markConstantRange(ConstantRange NewR,
                          MergeOptions Opts = MergeOptions()) {
+    assert(!NewR.isEmptySet() && "should only be called for non-empty sets");
+
     if (NewR.isFullSet())
       return markOverdefined();
 
     ValueLatticeElementTy OldTag = Tag;
     ValueLatticeElementTy NewTag =
         (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef)
             ? constantrange_including_undef
             : constantrange;
     if (isConstantRange()) {
-      if (NewR.isEmptySet())
-        return markOverdefined();
-
       Tag = NewTag;
       if (getConstantRange() == NewR)
         return Tag != OldTag;
 
       // Simple form of widening. If a range is extended multiple times, go to
       // overdefined.
       if (Opts.CheckWiden && ++NumRangeExtensions == 1)
         return markOverdefined();
 
       assert(NewR.contains(getConstantRange()) &&
              "Existing range must be a subset of NewR");
       Range = std::move(NewR);
       return true;
     }
 
     assert(isUnknown() || isUndef());
-    if (NewR.isEmptySet())
-      return markOverdefined();
 
     NumRangeExtensions = 0;
     Tag = NewTag;
     new (&Range) ConstantRange(std::move(NewR));
     return true;
   }
 
   /// Updates this object to approximate both this object and RHS. Returns
   /// true if this object has been changed.

llvm/lib/Analysis/LazyValueInfo.cpp

static ValueLatticeElement intersect(const ValueLatticeElement &A,
   if (!A.isConstantRange() || !B.isConstantRange()) {
     // TODO: Arbitrary choice, could be improved
     return A;
   }
 
   // Intersect two constant ranges
   ConstantRange Range =
       A.getConstantRange().intersectWith(B.getConstantRange());
-  // Note: An empty range is implicitly converted to overdefined internally.
-  // TODO: We could instead use Undefined here since we've proven a conflict
-  // and thus know this path must be unreachable.
+  // Note: An empty range is implicitly converted to unknown or undef depending
+  // on MayIncludeUndef internally.
   return ValueLatticeElement::getRange(
       std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() |
                             B.isConstantRangeIncludingUndef());
 }
 
 //===----------------------------------------------------------------------===//
 //                          LazyValueInfoCache Decl
 //===----------------------------------------------------------------------===//

llvm/test/Transforms/CorrelatedValuePropagation/sub.ll

 }
 
 define void @test2(i32 %a) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[A:%.*]], -1
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[A]], 1
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 [[A]], 1
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp = icmp ugt i32 %a, -1
   br i1 %cmp, label %bb, label %exit
 

llvm/test/Transforms/SCCP/widening.ll

 ; IPSCCP-NEXT:    br i1 [[TMP34]], label [[BB35:%.*]], label [[BB37:%.*]]
 ; IPSCCP:       bb35:
 ; IPSCCP-NEXT:    [[TMP36:%.*]] = getelementptr inbounds i8, i8* [[TMP32]], i64 1
 ; IPSCCP-NEXT:    br label [[BB66:%.*]]
 ; IPSCCP:       bb37:
 ; IPSCCP-NEXT:    [[C_2:%.*]] = icmp eq i32 [[TMP11]], 8
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[BB39:%.*]], label [[BB58:%.*]]
 ; IPSCCP:       bb39:
-; IPSCCP-NEXT:    [[TMP40:%.*]] = add nsw i32 [[TMP11]], -1
 ; IPSCCP-NEXT:    [[TMP41:%.*]] = trunc i32 [[TMP3]] to i16
 ; IPSCCP-NEXT:    store i16 [[TMP41]], i16* bitcast ([4 x i8]* @global.11 to i16*), align 1
 ; IPSCCP-NEXT:    [[TMP42:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
-; IPSCCP-NEXT:    [[TMP43:%.*]] = add i32 [[TMP7]], [[TMP40]]
+; IPSCCP-NEXT:    [[TMP43:%.*]] = add i32 [[TMP7]], 7
 ; IPSCCP-NEXT:    [[TMP44:%.*]] = mul i32 [[TMP43]], 4
 ; IPSCCP-NEXT:    [[TMP45:%.*]] = add i32 [[TMP44]], 2
 ; IPSCCP-NEXT:    [[TMP46:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP42]], i32 [[TMP45]])
 ; IPSCCP-NEXT:    [[TMP47:%.*]] = load i8, i8* [[TMP46]], align 1
 ; IPSCCP-NEXT:    [[TMP48:%.*]] = zext i8 [[TMP47]] to i32
 ; IPSCCP-NEXT:    [[TMP49:%.*]] = sub i32 [[TMP43]], 1
 ; IPSCCP-NEXT:    [[TMP50:%.*]] = mul i32 [[TMP49]], 4
 ; IPSCCP-NEXT:    [[TMP51:%.*]] = add i32 [[TMP50]], 2
 ; IPSCCP-NEXT:    [[TMP52:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP42]], i32 [[TMP51]])
 ; IPSCCP-NEXT:    [[TMP53:%.*]] = load i8, i8* [[TMP52]], align 1
 ; IPSCCP-NEXT:    [[TMP54:%.*]] = zext i8 [[TMP53]] to i32
 ; IPSCCP-NEXT:    [[TMP55:%.*]] = icmp sgt i32 [[TMP48]], [[TMP54]]
 ; IPSCCP-NEXT:    br i1 [[TMP55]], label [[BB56:%.*]], label [[BB60:%.*]]
 ; IPSCCP:       bb56:
-; IPSCCP-NEXT:    [[TMP57:%.*]] = add nsw i32 [[TMP40]], -1
 ; IPSCCP-NEXT:    br label [[BB60]]
 ; IPSCCP:       bb58:
 ; IPSCCP-NEXT:    [[TMP59:%.*]] = bitcast i16* [[TMP33]] to i8*
 ; IPSCCP-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 getelementptr inbounds ([4 x i8], [4 x i8]* @global.11, i64 0, i64 0), i8* align 2 [[TMP59]], i64 4, i1 false)
 ; IPSCCP-NEXT:    br label [[BB60]]
 ; IPSCCP:       bb60:
-; IPSCCP-NEXT:    [[TMP61:%.*]] = phi i32 [ [[TMP57]], [[BB56]] ], [ [[TMP40]], [[BB39]] ], [ [[TMP11]], [[BB58]] ]
+; IPSCCP-NEXT:    [[TMP61:%.*]] = phi i32 [ 6, [[BB56]] ], [ 7, [[BB39]] ], [ [[TMP11]], [[BB58]] ]
 ; IPSCCP-NEXT:    [[TMP62:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
 ; IPSCCP-NEXT:    [[TMP63:%.*]] = add i32 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP64:%.*]] = mul i32 [[TMP63]], 4
 ; IPSCCP-NEXT:    [[TMP65:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP62]], i32 [[TMP64]])
 ; IPSCCP-NEXT:    br label [[BB66]]
 ; IPSCCP:       bb66:
 ; IPSCCP-NEXT:    [[TMP67:%.*]] = phi i8* [ [[TMP36]], [[BB35]] ], [ null, [[BB60]] ]
 ; IPSCCP-NEXT:    ret i8* [[TMP67]]