[LVI] Make use of 'assume'-provided data

[junparser]

Summary

This patch fix regression showed in https://bugs.llvm.org/show_bug.cgi?id=45686.
It improved LVI in two ways: 1) analysis value in entry block. 2) combine assumptions with value range when solve selectInst in solveBlockValueSelect

TestPlan: check-llvm

[fhahn]

It improved LVI in two ways: 1) analysis value in entry block. 2) combine assumptions with value range when solve selectInst in solveBlockValueSelect

It would probably be best to submit this as 2 separate patches.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1810

This will result in incorrect handling of pointers, as the miscompiles in non-null.ll show. This would need D69914 to be reapplied first. Additionally it doesn't really make sense to limit this to the entry block, this should be using the block value for everything (that would be D69686).

[junparser]

since we still need discuss about the invoke of getValueInBlock, I'll split this patch into two parts.

llvm/lib/Analysis/LazyValueInfo.cpp

1810

thanks for point this. I have not notice handling of pointers.
As for limit this to entry block. it is the same reason as you mentioned in D69686 (the different order of computing block value) which is not a issue in entry block.

[fhahn]

In D81544#2084620, @junparser wrote:

since we still need discuss about the invoke of getValueInBlock, I'll split this patch into two parts.

I think this case could also be handled naturally by IPSCCP using PredicateInfo. Currently does only use range info from conditional branches, but I don't think there's any reason for not also using info from assume predicates, other than me not having time to implement it yet. If you want to give it a try, it would need to be added here: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/SCCP.cpp#L1243

[junparser]

In D81544#2084732, @fhahn wrote:

In D81544#2084620, @junparser wrote:

since we still need discuss about the invoke of getValueInBlock, I'll split this patch into two parts.

I think this case could also be handled naturally by IPSCCP using PredicateInfo. Currently does only use range info from conditional branches, but I don't think there's any reason for not also using info from assume predicates, other than me not having time to implement it yet. If you want to give it a try, it would need to be added here: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/SCCP.cpp#L1243

Thanks for the info. I'll check later.

[fhahn]

In D81544#2087285, @junparser wrote:

In D81544#2084732, @fhahn wrote:

In D81544#2084620, @junparser wrote:

since we still need discuss about the invoke of getValueInBlock, I'll split this patch into two parts.

I think this case could also be handled naturally by IPSCCP using PredicateInfo. Currently does only use range info from conditional branches, but I don't think there's any reason for not also using info from assume predicates, other than me not having time to implement it yet. If you want to give it a try, it would need to be added here: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/SCCP.cpp#L1243

Thanks for the info. I'll check later.

Great, please feel free to reach out in case there are any questions.

llvm/lib/Analysis/LazyValueInfo.cpp

 Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
     SelectInst *SI, BasicBlock *BB) {
   // Recurse on our inputs if needed
   Optional<ValueLatticeElement> OptTrueVal =
       getBlockValue(SI->getTrueValue(), BB);
   if (!OptTrueVal)
     return None;
   ValueLatticeElement &TrueVal = *OptTrueVal;
+  intersectAssumeOrGuardBlockValueConstantRange(SI->getTrueValue(), TrueVal,
+                                                SI);
 
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
   if (TrueVal.isOverdefined())
     return ValueLatticeElement::getOverdefined();
 
   Optional<ValueLatticeElement> OptFalseVal =
       getBlockValue(SI->getFalseValue(), BB);
   if (!OptFalseVal)
     return None;
   ValueLatticeElement &FalseVal = *OptFalseVal;
+  intersectAssumeOrGuardBlockValueConstantRange(SI->getFalseValue(), FalseVal,
+                                                SI);
 
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
   if (FalseVal.isOverdefined())
     return ValueLatticeElement::getOverdefined();
 
   if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
     const ConstantRange &TrueCR = TrueVal.getConstantRange();
LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
   // we can.
   // We limit the search to one step backwards from the current BB and value.
   // We could consider extending this to search further backwards through the
   // CFG and/or value graph, but there are non-obvious compile time vs quality
   // tradeoffs.
   if (CxtI) {
     BasicBlock *BB = CxtI->getParent();
 
-    // Function entry or an unreachable block.  Bail to avoid confusing
-    // analysis below.
+    // Analysis value in function entry.
+    if (BB == &BB->getParent()->getEntryBlock()) {
+      ValueLatticeElement Result =
+          getImpl(PImpl, AC, &DL).getValueInBlock(V, BB, CxtI);
+      return getPredicateResult(Pred, C, Result, DL, TLI);
+    }
+
+    // An unreachable block.  Bail to avoid confusing analysis below.
     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
     if (PI == PE)
       return Unknown;
 
     // If V is a PHI node in the same block as the context, we need to ask
     // questions about the predicate as applied to the incoming value along
     // each edge. This is useful for eliminating cases where the predicate is
     // known along all incoming edges.

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 
 define i1 @test12(i32 %x) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i64 [[ZEXT]], 7
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i64 [[MUL]], 32
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[SHR]] to i32
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[TRUNC]], 7
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %zext = zext i32 %x to i64
   %mul = mul nuw i64 %zext, 7
   %shr = lshr i64 %mul, 32
   %trunc = trunc i64 %shr to i32
   %cmp = icmp ult i32 %trunc, 7
   ret i1 %cmp
 }
 
 define i1 @test13(i8 %x, i64* %p) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT]], 128
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[ADD]], 384
 ; CHECK-NEXT:    store i64 [[ADD]], i64* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %zext = zext i8 %x to i64
   %add = add nuw nsw i64 %zext, 128
   %cmp = icmp ult i64 %add, 384
   ; Without this extra use, InstSimplify could handle this
   store i64 %add, i64* %p
   ret i1 %cmp
 }

llvm/test/Transforms/CorrelatedValuePropagation/non-null.ll

bb:
   icmp ne i8* %ptr, null
   ret void
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i1)
 
 define void @test4(i8* %dest, i8* %src) {
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* [[DEST:%.*]], i8* [[SRC:%.*]], i32 1, i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* nonnull [[DEST:%.*]], i8* nonnull [[SRC:%.*]], i32 1, i1 false)
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 1, i1 false)
   br label %bb
 bb:
   icmp ne i8* %dest, null
bb:
   icmp ne i8* %dest, null
   icmp ne i8* %src, null
   ret void
 }
 
 declare void @llvm.memmove.p0i8.p0i8.i32(i8*, i8*, i32, i1)
 define void @test5(i8* %dest, i8* %src) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i32(i8* [[DEST:%.*]], i8* [[SRC:%.*]], i32 1, i1 false)
+; CHECK-NEXT:    call void @llvm.memmove.p0i8.p0i8.i32(i8* nonnull [[DEST:%.*]], i8* nonnull [[SRC:%.*]], i32 1, i1 false)
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 1, i1 false)
   br label %bb
 bb:
   icmp ne i8* %dest, null
bb:
   icmp ne i8* %dest, null
   icmp ne i8* %src, null
   ret void
 }
 
 declare void @llvm.memset.p0i8.i32(i8*, i8, i32, i1)
 define void @test6(i8* %dest) {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* [[DEST:%.*]], i8 -1, i32 1, i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* nonnull [[DEST:%.*]], i8 -1, i32 1, i1 false)
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i32(i8* %dest, i8 255, i32 1, i1 false)
   br label %bb
 bb:
   icmp ne i8* %dest, null

llvm/test/Transforms/JumpThreading/assume.ll

 
 normal:
   ret void
 
 error:
   store atomic i32 0, i32* @g unordered, align 4
   ret void
 }
+
+define void @can_fold_assume5(i32, i32, i1 zeroext) {
+; CHECK-LABEL: can_fold_assume5
+; CHECK: @llvm.assume
+; CHECK: @llvm.assume
+; CHECK-NOT: br
+; CHECK-NOT: @dummy(i1 true)
+; CHECK-NEXT: ret void
+  %4 = icmp slt i32 %0, 234
+  tail call void @llvm.assume(i1 %4)
+  %5 = icmp sgt i32 %1, 789
+  tail call void @llvm.assume(i1 %5)
+  %6 = select i1 %2, i32 %0, i32 %1
+  %7 = add i32 %6, -234
+  %8 = icmp ult i32 %7, 556
+  br i1 %8, label %label1, label %label2
+
+label1:
+  tail call void @dummy(i1 true)
+  br label %label2
+
+label2:
+  ret void
+}
+
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1) #1
 
 declare void @bar(...)
 
 declare void @car(...)
 
 attributes #0 = { nounwind uwtable }
 attributes #1 = { nounwind }