[ValueTracking] Teach isKnownNonNullFromDominatingCondition about AND

[mkazantsev]

Summary

isKnownNonNullFromDominatingCondition is able to prove non-null basing on br or guard
by %p != null condition, but is unable to do so basing on (%p != null) && %other_cond.
This patch allows it to do so.

[xbolva00]

test/Transforms/LICM/hoist-deref-load.ll

601 ↗

(On Diff #158699)

check

[mkazantsev]

Fixed typos in test's comments.

[xbolva00]

I was wondering where is a good place for this: https://bugs.llvm.org/show_bug.cgi?id=38349 (in the true block, we know some info about bits of x, so this info should be propagated to the whole block)

[mkazantsev]

Here we are dealing with i1 AND only, so it should not be relevant here. The example in this bug looks like something to handle in InstCombine.

[reames]

LGTM

[mkazantsev]

This patch has exposed sanitizer failures, likely something that already existed and now got exposed. http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/14348. Investigating.

llvm/trunk/lib/Analysis/ValueTracking.cpp

for (auto *U : V->users()) {
 
     // Consider only compare instructions uniquely controlling a branch
     CmpInst::Predicate Pred;
     if (!match(const_cast<User *>(U),
                m_c_ICmp(Pred, m_Specific(V), m_Zero())) ||
         (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE))
       continue;
 
+    SmallVector<const User *, 4> WorkList;
+    SmallPtrSet<const User *, 4> Visited;
     for (auto *CmpU : U->users()) {
-      if (const BranchInst *BI = dyn_cast<BranchInst>(CmpU)) {
+      assert(WorkList.empty() && "Should be!");
+      if (Visited.insert(CmpU).second)
+        WorkList.push_back(CmpU);
+
+      while (!WorkList.empty()) {
+        auto *Curr = WorkList.pop_back_val();
+
+        // If a user is an AND, add all its users to the work list. We only
+        // propagate "pred != null" condition through AND because it is only
+        // correct to assume that all conditions of AND are met in true branch.
+        // TODO: Support similar logic of OR and EQ predicate?
+        if (Pred == ICmpInst::ICMP_NE)
+          if (auto *BO = dyn_cast<BinaryOperator>(Curr))
+            if (BO->getOpcode() == Instruction::And) {
+              for (auto *BOU : BO->users())
+                if (Visited.insert(BOU).second)
+                  WorkList.push_back(BOU);
+              continue;
+            }
+
+        if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
           assert(BI->isConditional() && "uses a comparison!");
 
           BasicBlock *NonNullSuccessor =
               BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0);
           BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
           if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
             return true;
         } else if (Pred == ICmpInst::ICMP_NE &&
-                 match(CmpU, m_Intrinsic<Intrinsic::experimental_guard>()) &&
-                 DT->dominates(cast<Instruction>(CmpU), CtxI)) {
+                   match(Curr, m_Intrinsic<Intrinsic::experimental_guard>()) &&
+                   DT->dominates(cast<Instruction>(Curr), CtxI)) {
           return true;
         }
       }
     }
+  }
 
   return false;
 }
 
 /// Does the 'Range' metadata (which must be a valid MD_range operand list)
 /// ensure that the value it's attached to is never Value?  'RangeType' is
 /// is the type of the value described by the range.
 static bool rangeMetadataExcludesValue(const MDNode* Ranges, const APInt& Value) {

llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll

for.inc:                                          ; preds = %for.body, %if.then
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.inc, %entry, %entry
   call void(i1, ...) @llvm.experimental.guard(i1 %not_null) [ "deopt"() ]
   ret void
 }
 
+; Check that branch by condition "null check AND something" allows to hoist the
+; load.
+define void @test14(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 {
+
+; CHECK-LABEL: @test14
+; CHECK: load i32, i32* %c, align 4
+; CHECK: for.body:
+
+entry:
+  %not_null = icmp ne i32* %c, null
+  %dummy_and = and i1 %not_null, %dummy_cond
+  br i1 %dummy_and, label %not.null, label %for.end
+
+not.null:
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %not.null, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry, %not.null
+  ret void
+}
+
+; Check that guard by condition "null check AND something" allows to hoist the
+; load.
+define void @test15(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 {
+
+; CHECK-LABEL: @test15
+; CHECK: load i32, i32* %c, align 4
+; CHECK: for.body:
+
+entry:
+  %not_null = icmp ne i32* %c, null
+  %dummy_and = and i1 %not_null, %dummy_cond
+  call void(i1, ...) @llvm.experimental.guard(i1 %dummy_and) [ "deopt"() ]
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret void
+}
+
+; Ensure that (c == null && other_cond) does not automatically mean that c is
+; non-null in false branch. So the condition ((c == null && other_cond) == false)
+; is not sufficient to conclude that c != null.
+define void @test16(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 {
+
+; CHECK-LABEL: @test16
+; CHECK: for.body:
+; CHECK: load i32, i32* %c, align 4
+
+entry:
+  %not_null = icmp eq i32* %c, null
+  %dummy_and = and i1 %not_null, %dummy_cond
+  br i1 %dummy_and, label %for.end, label %not.null
+
+not.null:
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %not.null, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry, %not.null
+  ret void
+}
+
+; Ensure that (c == null && other_cond) does not automatically mean that c is
+; non-null in false branch. So the condition ((c == null && other_cond) == false)
+; is not sufficient to conclude that c != null.
+define void @test17(i32* noalias %a, i32* %b, i32* dereferenceable_or_null(4) %c, i32 %n, i1 %dummy_cond) #0 {
+
+; CHECK-LABEL: @test17
+; CHECK: for.body:
+; CHECK: load i32, i32* %c, align 4
+
+entry:
+  %not_null = icmp eq i32* %c, null
+  %dummy_and = and i1 %not_null, %dummy_cond
+  call void(i1, ...) @llvm.experimental.guard(i1 %dummy_and) [ "deopt"() ]
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.end, label %for.body
+
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret void
+}
+
 attributes #0 = { nounwind uwtable }
 !0 = !{i64 4}