[LVI] Meet rules for non-null pointers

[reames]

Summary

The patch itself is fairly straight-forward, it simply extends LVI conservative meet operator to remember non-null facts when merging non-null constants.

However, the fact I had to write this is really making me question the value of pointer types in LVI as a whole. The lack of any decent meet rule basically means that pointer handling in LVI reduces to equality propagation and a dereferenceability based non-null analysis. Given GVN implements a version of the former (minus the meet of two constants case), I'm wondering whether pointers should just be removed from LVI and handled separately. I want to stew on that a bit further before actually landing this patch.

[reames]

This turns out to be a terrible idea as written. I realized after some reflection that I was essentially adding another state into the lattice and reused the not-constant state to represent both it's original meaning and the new state. In particular, this patch would allow a constant to fall to a non-constant before reaching overdefined. That's a new state transition not previously allowed..

The optimization power might be worth salvaging somewhere else; possibly as a null check specific analysis? I'm noticing in this code that floats, pointers, and integers get essentially disjoint results despite sharing a common infrastructure. (We never use results from one domain to influence results from another.) I'm increasingly thinking we need to split the analysis to reflect that. It might be worth sharing some code, but I'm also thinking about entirely different framings for the non-null analysis which is the primary purpose of the pointer tracking. Something to think about further...

lib/Analysis/LazyValueInfo.cpp

if (isUndefined()) {
       Range = RHS.Range;
       return true;
     }
 
     if (isConstant()) {
       if (RHS.isConstant()) {
         if (Val == RHS.Val)
           return false;
+
+        PointerType *PT = dyn_cast<PointerType>(Val->getType());
+        if (PT && isKnownNonNull(Val) && isKnownNonNull(RHS.Val))
+          return markNotConstant(ConstantPointerNull::get(PT));
+        
         return markOverdefined();
       }
 
       if (RHS.isNotConstant()) {
         if (Val == RHS.Val)
           return markOverdefined();
+
+        PointerType *PT = dyn_cast<PointerType>(Val->getType());
+        if (PT && isa<ConstantPointerNull>(RHS.Val) && isKnownNonNull(Val))
+          return markNotConstant(ConstantPointerNull::get(PT));
+        
         return markOverdefined();
       }
 
       return markOverdefined();
     }
 
     if (isNotConstant()) {
       if (RHS.isConstant()) {
         if (Val == RHS.Val)
           return markOverdefined();
+
+        PointerType *PT = dyn_cast<PointerType>(Val->getType());
+        if (PT && isa<ConstantPointerNull>(Val) && isKnownNonNull(RHS.Val))
+          return false;
+        
         return markOverdefined();
       }
 
       if (RHS.isNotConstant()) {
         if (Val == RHS.Val)
           return false;
         return markOverdefined();
       }

test/Transforms/CorrelatedValuePropagation/select.ll

; CHECK: ret i1 true
   %res = icmp slt i32 %sel, 254
   ret i1 %res
 
 exit:
 ; CHECK-LABEL: exit:
 ; CHECK: ret i1 true
   ret i1 true
 }
+
+define i1 @test7(i1 %unknown, i32* nonnull %p1, i32* nonnull %p2 ) {
+; CHECK-LABEL: @test7
+  %sel = select i1 %unknown, i32* %p1, i32* %p2
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 true
+  %res = icmp ne i32* %sel, null
+  ret i1 %res
+}
+@g1 = external global i32
+@g2 = external global i32
+
+define i1 @test8a(i1 %unknown, i32* nonnull %p1) {
+; CHECK-LABEL: @test8
+  %sel = select i1 %unknown, i32* %p1, i32* @g1
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 true
+  %res = icmp ne i32* %sel, null
+  ret i1 %res
+}
+
+define i1 @test8b(i1 %unknown, i32* nonnull %p1) {
+; CHECK-LABEL: @test8
+  %sel = select i1 %unknown, i32* %p1, i32* @g1
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 true
+  %res = icmp ne i32* %sel, null
+  ret i1 %res
+}
+
+define i1 @test9(i1 %unknown) {
+; CHECK-LABEL: @test9
+  %sel = select i1 %unknown, i32* @g1, i32* @g2
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 true
+  %res = icmp ne i32* %sel, null
+  ret i1 %res
+}