[SimplifyCFG] Add early bailout if Use is not in same BB.

[fhahn]

Summary

Without this patch, passingValueIsAlwaysUndefined will iterate over all
instructions from I to the end of the basic block, even if the use is
outside the block.

This patch adds an early bail out, if the use instruction is outside I's
BB. This can greatly reduce compile-time in cases where very large basic
blocks are involved, with a large number of PHI nodes and incoming
values.

Note that the refactoring makes the handling of the case where I is a
phi and Use is in PHI more explicit as well: for phi nodes, we can also
directly bail out. In the existing code, we would iterate until we reach
the end and return false.

I could add a test case that shows the compile-time improvement, but it
would be quite large.

Based on an earlier patch by Matt Wala.

[fhahn]

Remove UseI variable, use Use instead.

[RKSimon]

SGTM - might an alternative to a test be to run it on https://llvm-compile-time-tracker.com ?

[mkazantsev]

I don't understand the old code. Why does it look at one user? I thought the order of uses is undefined, and whatever checks are done for just one user and not done for the others may be a source of non-determinism.

[nikic]

In D113293#3114654, @mkazantsev wrote:

I don't understand the old code. Why does it look at one user? I thought the order of uses is undefined, and whatever checks are done for just one user and not done for the others may be a source of non-determinism.

The order is deterministic, but usually arbitrary (see uselistorder in IR and -preserve-(bc|ll)-uselistorder).

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6530–6535

Can be cast, user of instruction is always instruction.

6543

We have isGuaranteedToTransferExecutionToSuccessor() variants that accept iterators in ValueTracking, and also enforce a ScanLimit (default 32). That should ensure that there are no pathological cases even if they are in the same block.

[fhahn]

Updated to use cast instead of dyn_cast.

In D113293#3113417, @RKSimon wrote:

SGTM - might an alternative to a test be to run it on https://llvm-compile-time-tracker.com ?

Done: http://llvm-compile-time-tracker.com/compare.php?from=e3bfb6a14646fd3b344c491a5f46aaebd43090a7&to=2ea682d8c75956531a894e38af397caf627b3882&stat=instructions

There are a few small but notable improvements:

NewPM-O3:

ClamAV	71699M	71567M (-0.18%)

NewPM-ReleaseLTO-g:

kimwitu++	85293M	85171M (-0.14%)

[fhahn]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6530–6535

updated, thanks!

6543

I did that with the following results: http://llvm-compile-time-tracker.com/compare.php?from=29c1c85c4e1dfe663bd9e7424d021283f9dc3254&to=2c6b1eed0c7f8e933e7666bc50eb390bbfccc039&stat=instructions

I'd like to keep this out of the current change though, as this may impact the generated code (there are a few binary changes even for CTMark), while the current patch should be NFC with respect to codegen.

[lebedev.ri]

LGTM

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6530–6535

Can also drop the !Use check.

[fhahn]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6530–6535

Done in the committed version, thanks!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified) {
   if (!C)
     return false;
 
   if (I->use_empty())
     return false;
 
   if (C->isNullValue() || isa<UndefValue>(C)) {
     // Only look at the first use, avoid hurting compile time with long uselists
-    User *Use = *I->user_begin();
+    auto *Use = cast<Instruction>(*I->user_begin());
+    // Bail out if Use is not in the same BB as I or Use == I or Use comes
+    // before I in the block. The latter two can be the case if Use is a PHI
+    // node.
+    if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
+      return false;
 
     // Now make sure that there are no instructions in between that can alter
     // control flow (eg. calls)
-    for (BasicBlock::iterator
-             i = ++BasicBlock::iterator(I),
-             UI = BasicBlock::iterator(dyn_cast<Instruction>(Use));
-         i != UI; ++i) {
-      if (i == I->getParent()->end())
-        return false;
-      if (!isGuaranteedToTransferExecutionToSuccessor(&*i))
-        return false;
-    }
+    auto InstrRange =
+        make_range(std::next(I->getIterator()), Use->getIterator());
+    if (any_of(InstrRange, [](Instruction &I) {
+          return !isGuaranteedToTransferExecutionToSuccessor(&I);
+        }))
 
     // Look through GEPs. A load from a GEP derived from NULL is still undefined
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
       if (GEP->getPointerOperand() == I) {
         if (!GEP->isInBounds() || !GEP->hasAllZeroIndices())
           PtrValueMayBeModified = true;
         return passingValueIsAlwaysUndefined(V, GEP, PtrValueMayBeModified);
       }