[IsKnownNonZero] Handle the case with non-constant phi nodes

[skatkov]

Summary

Handle the case when all inputs of phi are proven to be non zero.

Constants are checked in beginning of this method before check for depth of recursion,
so it is a partial case of non-constant phi.

Recursion depth is already handled by the function.

[aqjune]

LGTM

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2567

It is necessary to adjust the context instruction in Q to be the terminator of the incoming edge here (see what computeKnownBits does for example).

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

2567

Does it mean that we need updates in a few other places as well (orthogonally from this patch)? e.g., https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/ValueTracking.cpp#L2970

[skatkov]

Thank you for review.

Is it better?

[nikic]

Thanks for the update, the new version should be correct. However, it can also be expensive, because we may loop through a phi multiple times until the depth limit is exhausted. I would suggest to follow the same implementation approach as computeKnownBits() does in https://github.com/llvm/llvm-project/blob/d2166076b882e38becf3657ea830ffd2b6a5695e/llvm/lib/Analysis/ValueTracking.cpp#L1574-L1606. Namely to perform the recursive call with MaxDepth - 1. (I would also suggest to handle your TODO right away, to have parity with the known bits code.)

Edit: Current compile-time results for reference: https://llvm-compile-time-tracker.com/compare.php?from=f161e84c10b6eb2255345ebfaaa2bbadb4b0fe2a&to=541eefb28e624a99b22408b4322720bc6cd6972f&stat=instructions We should be able to do better than that.

llvm/lib/Analysis/ValueTracking.cpp

2567

Yes, looks like that one needs to be fixed as well.

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

2567

Made a patch here: D88360.

[skatkov]

In D88276#2295622, @nikic wrote:

Thanks for the update, the new version should be correct. However, it can also be expensive, because we may loop through a phi multiple times until the depth limit is exhausted. I would suggest to follow the same implementation approach as computeKnownBits() does in https://github.com/llvm/llvm-project/blob/d2166076b882e38becf3657ea830ffd2b6a5695e/llvm/lib/Analysis/ValueTracking.cpp#L1574-L1606. Namely to perform the recursive call with MaxDepth - 1. (I would also suggest to handle your TODO right away, to have parity with the known bits code.)

Edit: Current compile-time results for reference: https://llvm-compile-time-tracker.com/compare.php?from=f161e84c10b6eb2255345ebfaaa2bbadb4b0fe2a&to=541eefb28e624a99b22408b4322720bc6cd6972f&stat=instructions We should be able to do better than that.

Well, I can restrict the depth for phi nodes only to one level but it seems it causes the strange correlation to max depth. I tend to think that it would be better to increase depth to number of phi operands than restrict it to one level. In this case we can treat max depth as number of invocation of function. So it would be linear.

Please also note that right before phi handling we have a switch handling. It does not use one level depth as well as it does not modify the context instruction while select is actually can be considered as equivalent of phi node. Should be switch fixed as well?

[skatkov]

please take a look. Still think that restriction to one level is too strong but let's start with it.

[skatkov]

Do not go to recursion if we handle this phi node with the same context. If context is different, the answer might be different in theory.

[jdoerfert]

@nikic thanks for catching this, these are a pain to debug later on (I remember D69571). That said, we should probably add a test that shows why this is necessary. Can you take a look at the test in D71181 and https://reviews.llvm.org/D60846#1497243 to make sure we have a similar one for coverage here?

Please also note that right before phi handling we have a switch handling. It does not use one level depth as well as it does not modify the context instruction while select is actually can be considered as equivalent of phi node. Should be switch fixed as well?

Select do not require a change in context (as far as I can tell). A PHI is "assigned/evaluated" on the incoming edge, not in the PHI block. The key difference is that the incoming value does not dominate the phi while this has to be the case for the select.

---

In D88276#2297244, @skatkov wrote:

please take a look. Still think that restriction to one level is too strong but let's start with it.

(Disclaimer, I'm obviously biased towards the Attributor.)
TBH, I don't think such logic belongs here anyway. The problem is that we do not "cache" results but simply recompute them, given use-def cycles that can spiral out of control.
If you run the Attributor it will deduce and annotate various locations with nonnull, if we are missing some we can talk about ways to improve it.

---

Nit: typo in the commit message.
Nit: consider Q.getWithInstruction, no strong feelings.

[skatkov]

In D88276#2297343, @jdoerfert wrote:

Nit: consider Q.getWithInstruction, no strong feelings.

Q is not SimplifyQuery here, how I could take a getWithInstruction then?

[jdoerfert]

In D88276#2297356, @skatkov wrote:

In D88276#2297343, @jdoerfert wrote:

Nit: consider Q.getWithInstruction, no strong feelings.

Q is not SimplifyQuery here, how I could take a getWithInstruction then?

You won't, just ignore that part ;)

[skatkov]

In D88276#2297358, @jdoerfert wrote:

In D88276#2297356, @skatkov wrote:

In D88276#2297343, @jdoerfert wrote:

Nit: consider Q.getWithInstruction, no strong feelings.

Q is not SimplifyQuery here, how I could take a getWithInstruction then?

You won't, just ignore that part ;)

I did :)

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2569

Why the RecQ.CxtI == Q.CxtI check here? Shouldn't we always be able to skip, regardless of context?

[skatkov]

llvm/lib/Analysis/ValueTracking.cpp

2569

Not sure, just to be conservative. I have no some concrete example. Can remove until some example is found.

[skatkov]

git rid of additional check for context instruction.

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

if (PN->getNumIncomingValues() == 2) {
           if (Q.IIQ.UseInstrInfo &&
               (match(Induction, m_NSWAdd(m_Specific(PN), m_ConstantInt(X))) ||
                match(Induction, m_NUWAdd(m_Specific(PN), m_ConstantInt(X)))) &&
               !X->isNegative())
             return true;
         }
       }
     }
-    // Check if all incoming values are non-zero constant.
-    bool AllNonZeroConstants = llvm::all_of(PN->operands(), [](Value *V) {
-      return isa<ConstantInt>(V) && !cast<ConstantInt>(V)->isZero();
+    // Check if all incoming values are non-zero using recursion.
+    Query RecQ = Q;
+    unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
+    bool AllNonZero = llvm::all_of(PN->operands(), [&](const Use &U) {
+      if (U.get() == PN)
+        return true;
+      RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
+      return isKnownNonZero(U.get(), DemandedElts, NewDepth, RecQ);
     });
-    if (AllNonZeroConstants)
+    if (AllNonZero)
       return true;
   }
   // ExtractElement
   else if (const auto *EEI = dyn_cast<ExtractElementInst>(V)) {
     const Value *Vec = EEI->getVectorOperand();
     const Value *Idx = EEI->getIndexOperand();
     auto *CIdx = dyn_cast<ConstantInt>(Idx);
     if (auto *VecTy = dyn_cast<FixedVectorType>(Vec->getType())) {

llvm/test/Transforms/InstCombine/phi.ll

 
 if.end:                                           ; preds = %if.else, %if.then
   %x.0 = phi i32 [ 1, %if.then ], [ 2, %if.else ]
   %or = or i32 %x.0, %a
   %cmp1 = icmp eq i32 %or, 0
   ret i1 %cmp1
 }
 
+define i1 @phi_allnonzerononconstant(i1 %c, i32 %a, i32* nonnull %b1, i32* nonnull %b2) {
+; CHECK-LABEL: @phi_allnonzerononconstant(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @dummy()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %c, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void @dummy()
+
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %x.0 = phi i32* [ %b1, %if.then ], [ %b2, %if.else ]
+  %cmp1 = icmp eq i32* %x.0, null
+  ret i1 %cmp1
+}
+
 declare void @dummy()
 
 define i1 @phi_knownnonzero_eq(i32 %n, i32 %s, i32* nocapture readonly %P) {
 ; CHECK-LABEL: @phi_knownnonzero_eq(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp slt i32 [[N:%.*]], [[S:%.*]]
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then: