[ValueTracking] Use Inst::comesBefore in isValidAssumeForCtx (NFC).

[fhahn]

Summary

D51664 added Instruction::comesBefore which should provide better
performance than the manual check.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

650–651

This condition is redundant, it's already checked above.

651

This should be if (Inv->comesBefore(CxtI)) return true, otherwise the reverse-direction scan below will be skipped.

[fhahn]

Remove unnecessary checks, do not skip the checks later on.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

652

Isn't the !DT condition still relevant here? If we have DT, then this was already covered by the domination check.

Generally, I think this code is a bit convoluted, and I think it would be clearer to rewrite along these lines:

BasicBlock *InvBB = Inv->getParent(), *CxtBB = CxtI->getParent();
if (InvBB != CxtBB) {
  if (DT)
    return DT->dominates(InvBB, CxtBB);
  else
    // We don't have a DT, but this trivially dominates.
    return InvBB == CxtBB->getSinglePredecessor();
}

// If Inv and CtxI are in the same block, check if the assume (Inv) is first
// in the BB.
if (Inv->comesBefore(CxtI))
  return true;

// Rest of the code...

[fhahn]

Generally, I think this code is a bit convoluted, and I think it would be clearer to rewrite along these lines.

Agreed, I've restructured the code a bit. It seemed a bit more straight forward to check and handle the case were both instructions are in the same BB up front, followed by the DT check. WDYT?

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
bool llvm::isValidAssumeForContext(const Instruction *Inv,
   // There are two restrictions on the use of an assume:
   //  1. The assume must dominate the context (or the control flow must
   //     reach the assume whenever it reaches the context).
   //  2. The context must not be in the assume's set of ephemeral values
   //     (otherwise we will use the assume to prove that the condition
   //     feeding the assume is trivially true, thus causing the removal of
   //     the assume).
 
-  if (DT) {
-    if (DT->dominates(Inv, CxtI))
-      return true;
-  } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) {
-    // We don't have a DT, but this trivially dominates.
+  if (Inv->getParent() == CxtI->getParent()) {
+    // If Inv and CtxI are in the same block, check if the assume (Inv) is first
+    // in the BB.
+    if (Inv->comesBefore(CxtI))
       return true;
-  }
-
-  // With or without a DT, the only remaining case we will check is if the
-  // instructions are in the same BB.  Give up if that is not the case.
-  if (Inv->getParent() != CxtI->getParent())
-    return false;
-
-  // If we have a dom tree, then we now know that the assume doesn't dominate
-  // the other instruction.  If we don't have a dom tree then we can check if
-  // the assume is first in the BB.
-  if (!DT) {
-    // Search forward from the assume until we reach the context (or the end
-    // of the block); the common case is that the assume will come first.
-    for (auto I = std::next(BasicBlock::const_iterator(Inv)),
-         IE = Inv->getParent()->end(); I != IE; ++I)
-      if (&*I == CxtI)
-        return true;
-  }
 
     // Don't let an assume affect itself - this would cause the problems
     // `isEphemeralValueOf` is trying to prevent, and it would also make
     // the loop below go out of bounds.
     if (Inv == CxtI)
       return false;
 
     // The context comes first, but they're both in the same block.
     // Make sure there is nothing in between that might interrupt
     // the control flow, not even CxtI itself.
     for (BasicBlock::const_iterator I(CxtI), IE(Inv); I != IE; ++I)
       if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
         return false;
 
     return !isEphemeralValueOf(Inv, CxtI);
   }
 
+  // Inv and CxtI are in different blocks.
+  if (DT) {
+    if (DT->dominates(Inv, CxtI))
+      return true;
+  } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) {
+    // We don't have a DT, but this trivially dominates.
+    return true;
+  }
+
+  return false;
+}
+
 static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) {
   // Use of assumptions is context-sensitive. If we don't have a context, we
   // cannot use them!
   if (!Q.AC || !Q.CxtI)
     return false;
 
   // Note that the patterns below need to be kept in sync with the code
   // in AssumptionCache::updateAffectedValues.