[BasicAA] Drop dependency on Loop Info. PR43276

[mkazantsev]

Summary

BasicAA stores a reference to LoopInfo inside. This imposes an implicit
requirement of keeping it up to date whenever we modify the IR (in particular,
whenever we modify terminators of blocks that belong to loops). Failing
to do so leads to incorrect state of the LoopInfo.

Because general AA does not require loop info updates and provides to API to
update it properly, the users of AA reasonably assume that there is no need to
update the loop info. It may be a reason of bugs, as example in PR43276 shows.

This patch drops dependence of BasicAA on LoopInfo to avoid this problem.

This may potentially pessimize the result of queries to BasicAA.

[nikic]

AA uses DT, so it will be affected by more than just deleted basic blocks, but probably in more subtle ways. How much would we lose by not using AA entirely?

[lebedev.ri]

Hm, why does the block actually end up being deleted?
DominatorTree/DomTreeUpdater is always present, and DomTreeUpdater is in lazy mode, so it doesn't apply changes/delete blocks immediately, but only when flushed.
But where does it get flushed? *That* seems like a bug.

[mkazantsev]

I think I gave wrong explanation to what's going on. It's not blocks being deleted, but some interaction between block deletion and caching of some loop data within the AA. I'll update the description accordingly.

[mkazantsev]

The real problem is that functions like MergeBasicBlockIntoOnlyPred may be applied to a loop block, and in fact make the affected block not part of the loop. No one updates the loop info inside the AA accordingly. Maybe we can fix it...

[mkazantsev]

Updated the description. In fact, it's not about dangling pointers. It doesn't matter if the block has physically been removed or not. The problem is that we never inform the AA that we
remove a block and it should be, in particular, wiped out of its loop info.

[lebedev.ri]

Would be nice to fix this for real, but not having a not-so-fun-to-debug bug is good-enough.
SGTM, thanks.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

456

Please add the same TLDR to the other AA = nullptr;.

[nikic]

I don't think this is an acceptable fix, even as a workaround. If this is really *just* about LoopInfo, we should be able to just drop the LoopInfo dependency in BasicAA, it's not particularly important. However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

I also really don't like the idea of dropping an analysis partway through, as that effectively makes our test coverage a lie. Tests naturally test transforms in isolation, but real programs will see many transforms applied in sequence. Transforms that work in tests will not actually work in practice. Dropping the AA dependency entirely would provide a more honest view of how this actually affects transformations and whether there is anything we can do to mitigate.

[mkazantsev]

In D98627#2628263, @nikic wrote:

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

[nikic]

In D98627#2628283, @mkazantsev wrote:

In D98627#2628263, @nikic wrote:

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

JumpThreading only uses DTU to preserve the DomTree for the pass manager, it never flushes the DTU during the execution of the pass itself. This means that AA may work on a stale DomTree.

[mkazantsev]

Looks like it's not a big deal indeed. No test has pessimized when BasicAA does not use LI anymore.

[lebedev.ri]

In D98627#2628394, @mkazantsev wrote:

Looks like it's not a big deal indeed. No test has pessimized when BasicAA does not use LI anymore.

BasicAA uses LoopInfo as compile time optimization, it won't (shouldn't) affect the results.

[mkazantsev]

In D98627#2628288, @nikic wrote:

In D98627#2628283, @mkazantsev wrote:

In D98627#2628263, @nikic wrote:

However, it's not at all obvious to me why this problem affects only LI and not DT. JumpThreading has many other places that use DTU, why do those not have to drop AA as well?

All relevant places take DTU, so the DomTree is kept up-to-date (under assumption that AA and the opt inself use the *same* dom tree, which is, frankly, not obvious).

I'll see what are the implications of dropping LI dependency in basic AA. Maybe it's indeed a way worth taking.

JumpThreading only uses DTU to preserve the DomTree for the pass manager, it never flushes the DTU during the execution of the pass itself. This means that AA may work on a stale DomTree.

I can't say for sure that there is no another bug. But with LI, the situation is pretty simple: we delete a block (for example, by merging it into its predecessor), which was a loop exiting block. Then, an attempt to get loop exits leads to crash.

Interactions with DT may happen to be correct, or may be indeed broken (and we are still to find a test that shows this).

[nikic]

Compile-time looks good: https://llvm-compile-time-tracker.com/compare.php?from=5fb43477dcacd6fca573699dd2691a17eae7dc7e&to=9aee05e989e04b0aae9a3cb283a93686ca630460&stat=instructions It's not super obvious to me why there are improvements in the LegacyPM configuration.

[nikic]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1691 ↗

(On Diff #330914)

nit: You can leave off the last argument, nullptr is the default.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (auto &BB : F) {
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
         DeleteDeadBlock(&BB, DTU);
         Changed = true;
+        // The alias analysis may use LoopInfo inside of it. When we remove
+        // a block, even if it's done lazily, the loop info may still consider
+        // it a part of some loop. Then, all interactions with this loop will
+        // potentially lead to incorrect behavior.
+        // TODO: Once we have API to inform the AA of loop changes, we should
+        // use it here.
+        AA = nullptr;
         continue;
       }
 
       // processBlock doesn't thread BBs with unconditional TIs. However, if BB
       // is "almost empty", we attempt to merge BB with its sole successor.
       auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
       if (BI && BI->isUnconditional()) {
         BasicBlock *Succ = BI->getSuccessor(0);
         if (
             // The terminator must be the only non-phi instruction in BB.
             BB.getFirstNonPHIOrDbg(true)->isTerminator() &&
             // Don't alter Loop headers and latches to ensure another pass can
             // detect and transform nested loops later.
             !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
             TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
           RemoveRedundantDbgInstrs(Succ, true);
           // BB is valid for cleanup here because we passed in DTU. F remains
           // BB's parent until a DTU->getDomTree() event.
           LVI->eraseBlock(&BB);
           Changed = true;
+          AA = nullptr;
         }
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   return EverChanged;
if (TI->isExceptionalTerminator() || TI->getNumSuccessors() != 1 ||
     return false;
 
   // If SinglePred was a loop header, BB becomes one.
   if (LoopHeaders.erase(SinglePred))
     LoopHeaders.insert(BB);
 
   LVI->eraseBlock(SinglePred);
   MergeBasicBlockIntoOnlyPred(BB, DTU);
+  AA = nullptr;
 
   // Now that BB is merged into SinglePred (i.e. SinglePred code followed by
   // BB code within one basic block `BB`), we need to invalidate the LVI
   // information associated with BB, because the LVI information need not be
   // true for all of BB after the merge. For example,
   // Before the merge, LVI info and code is as follows:
   // SinglePred: <LVI info1 for %p val>
   // %y = use of %p

llvm/test/Transforms/JumpThreading/pr43276.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -aa-pipeline=basic-aa -passes='require<loops>,jump-threading' | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = external global i8*
+
+define i32 @wibble() {
+; CHECK-LABEL: @wibble(
+; CHECK-NEXT:  bb19:
+; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr i8, i8* undef, i64 16
+; CHECK-NEXT:    [[TMP21:%.*]] = load atomic i8*, i8** @global unordered, align 8
+; CHECK-NEXT:    [[TMP22:%.*]] = getelementptr inbounds i8, i8* [[TMP21]], i64 936
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i8* [ [[TMP22]], [[BB19:%.*]] ], [ undef, [[BB2:%.*]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i8* [ [[TMP21]], [[BB19]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i8* [[TMP]] to i64*
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i8, i8* [[TMP4]], i64 848
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i8* [[TMP6]] to i8**
+; CHECK-NEXT:    br label [[BB11:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12:%.*]] = load atomic i8*, i8** [[TMP7]] unordered, align 8
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i8* [[TMP12]], null
+; CHECK-NEXT:    br i1 [[TMP13]], label [[BB17:%.*]], label [[BB16:%.*]]
+; CHECK:       bb16:
+; CHECK-NEXT:    store atomic i64 undef, i64* [[TMP5]] unordered, align 8
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb17:
+; CHECK-NEXT:    ret i32 undef
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br label %bb18
+
+bb2:                                              ; No predecessors!
+  br label %bb3
+
+bb3:                                              ; preds = %bb19, %bb2
+  %tmp = phi i8* [ %tmp22, %bb19 ], [ undef, %bb2 ]
+  %tmp4 = phi i8* [ %tmp21, %bb19 ], [ undef, %bb2 ]
+  %tmp5 = bitcast i8* %tmp to i64*
+  %tmp6 = getelementptr inbounds i8, i8* %tmp4, i64 848
+  %tmp7 = bitcast i8* %tmp6 to i8**
+  br label %bb11
+
+bb11:                                             ; preds = %bb16, %bb3
+  %tmp12 = load atomic i8*, i8** %tmp7 unordered, align 8
+  %tmp13 = icmp eq i8* %tmp12, null
+  br i1 %tmp13, label %bb17, label %bb14
+
+bb14:                                             ; preds = %bb11
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  br label %bb16
+
+bb16:                                             ; preds = %bb15
+  store atomic i64 undef, i64* %tmp5 unordered, align 8
+  br label %bb11
+
+bb17:                                             ; preds = %bb11
+  ret i32 undef
+
+bb18:                                             ; preds = %bb1
+  br label %bb19
+
+bb19:                                             ; preds = %bb18
+  %tmp20 = getelementptr i8, i8* undef, i64 16
+  %tmp21 = load atomic i8*, i8** @global unordered, align 8
+  %tmp22 = getelementptr inbounds i8, i8* %tmp21, i64 936
+  br label %bb3
+}
+
+define void @zot(i8* align 8 dereferenceable_or_null(16) %arg, i32 %arg1) {
+; CHECK-LABEL: @zot(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    ret void
+;
+bb:
+  ret void
+}

llvm/test/Transforms/JumpThreading/thread-loads.ll

 ; CHECK-NEXT:    i32 1, label [[SW_BB_I:%.*]]
 ; CHECK-NEXT:    i32 0, label [[SW_BB21_I:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb.i:
 ; CHECK-NEXT:    [[CALL_I62:%.*]] = call fastcc i32* @GenerateCheckEvasions()
 ; CHECK-NEXT:    store i32* [[CALL_I62]], i32** [[ARRAYIDX89]], align 8
 ; CHECK-NEXT:    [[L2:%.*]] = load i32, i32* [[ARRAYIDX185]], align 4
 ; CHECK-NEXT:    [[TOBOOL_I63:%.*]] = icmp eq i32 [[L2]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_I63]], label [[SW_BB21_I_THREAD:%.*]], label [[IF_THEN_I64:%.*]]
-; CHECK:       sw.bb21.i.thread:
-; CHECK-NEXT:    store i32 10, i32* [[PHASE]], align 8
-; CHECK-NEXT:    br label [[DO_BODY_PREHEADER_I67:%.*]]
+; CHECK-NEXT:    br i1 [[TOBOOL_I63]], label [[SW_BB21_I]], label [[IF_THEN_I64:%.*]]
 ; CHECK:       if.then.i64:
 ; CHECK-NEXT:    store i32 7, i32* [[PHASE]], align 8
 ; CHECK-NEXT:    store i32 [[L2]], i32* [[ARRAYIDX307]], align 4
 ; CHECK-NEXT:    [[CALL16_I:%.*]] = call fastcc i32 @ValidMove(i32 [[L2]])
 ; CHECK-NEXT:    [[TOBOOL17_I:%.*]] = icmp eq i32 [[CALL16_I]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL17_I]], label [[IF_ELSE_I65:%.*]], label [[CLEANUP]]
 ; CHECK:       if.else.i65:
 ; CHECK-NEXT:    call void @f65()
 ; CHECK-NEXT:    br label [[SW_BB21_I]]
 ; CHECK:       sw.bb21.i:
-; CHECK-NEXT:    [[L3_PR:%.*]] = load i32, i32* [[ARRAYIDX185]], align 4
 ; CHECK-NEXT:    store i32 10, i32* [[PHASE]], align 8
-; CHECK-NEXT:    [[TOBOOL27_I:%.*]] = icmp eq i32 [[L3_PR]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL27_I]], label [[DO_BODY_PREHEADER_I67]], label [[CLEANUP]]
+; CHECK-NEXT:    [[L3:%.*]] = load i32, i32* [[ARRAYIDX185]], align 4
+; CHECK-NEXT:    [[TOBOOL27_I:%.*]] = icmp eq i32 [[L3]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL27_I]], label [[DO_BODY_PREHEADER_I67:%.*]], label [[CLEANUP]]
 ; CHECK:       do.body.preheader.i67:
 ; CHECK-NEXT:    call void @f67()
 ; CHECK-NEXT:    ret i32 67
 ; CHECK:       cleanup:
 ; CHECK-NEXT:    call void @Cleanup()
 ; CHECK-NEXT:    ret i32 0
 ;
 entry: