Fix a missing memoryssa update in breakLoopBackedge

[reames]

Summary

This is a case I'd missed in 6a8237. The odd bit here is that missing the edge removal update seems to produce MemorySSA which verifies, but is still corrupt in a way which bothers following passes. I wasn't able to reduce a single pass test case, which is why the reported test case is taken as is.

Posting for review to make sure there's nothing "interesting" about the use of the updater classes. The invariants on these are a bit subtle, and I want a second opinion.

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

751

I think there may be a preference to let MSSAU also update DT for performance reasons, along the lines of:

if (MSSA)
  MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT, /*UpdateDT*/true);
else
  DT.applyUpdates({{DominatorTree::Delete, Latch, Header}});

But I'm not sure how important this is. @asbirlea will know...

[asbirlea]

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

llvm/lib/Transforms/Utils/LoopUtils.cpp

751

Yes, ideally, let the MSSAU handle DT updates as well.

I'll send a change to the MSSAUpdater shortly so it doesn't matter as much when only deleting edges. I'll be ok with the code as is after that change (right now, with this patch, the deleted edge is readded during the MSSA update and then redeleted).
In general, best practice is to have them updated together.

[asbirlea]

(a10409fe23c35a7eed0f39d12624af229d3877e1 resolves the way deleted edges are handled when there are no inserts)

[reames]

In D109068#2977909, @asbirlea wrote:

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

FYI, this is not the sole issue. I manually added a call to MSSA->verifyMemorySSA() unconditionally to the end of the pass, and it did not catch this.

[asbirlea]

In D109068#2978402, @reames wrote:

In D109068#2977909, @asbirlea wrote:

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

FYI, this is not the sole issue. I manually added a call to MSSA->verifyMemorySSA() unconditionally to the end of the pass, and it did not catch this.

I'm sorry, I didn't fully parse this.
Adding MSSA->verifyMemorySSA() unconditionally to the end of the pass will not catch this. You need to enable EXPENSIVE_CHECKS (or uncomment the ifdefs inside verifyOrderingDominationAndDefUses for this case, there's more in another verify method). Part of the verification is disabled, even in debug build.
Or "by not sole issue" did you mean there's an additional issue not fixed by this patch?

[reames]

In D109068#2978419, @asbirlea wrote:

In D109068#2978402, @reames wrote:

In D109068#2977909, @asbirlea wrote:

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

FYI, this is not the sole issue. I manually added a call to MSSA->verifyMemorySSA() unconditionally to the end of the pass, and it did not catch this.

I'm sorry, I didn't fully parse this.
Adding MSSA->verifyMemorySSA() unconditionally to the end of the pass will not catch this. You need to enable EXPENSIVE_CHECKS (or uncomment the ifdefs inside verifyOrderingDominationAndDefUses for this case, there's more in another verify method). Part of the verification is disabled, even in debug build.
Or "by not sole issue" did you mean there's an additional issue not fixed by this patch?

I'd meant that a missing call to verify memory SSA was not the sole issue. Your explanation explains why an expensive checks build found this, but local testing (on an asserts build) did not.

However, please change this. Calling verifyMemorySSA should not change behavior based on EXPENSIVE_CHECKS!! EXPENSIVE_CHECKS can decide whether to call verify, or even change a "how hard" flag to the verify routine, but a manual call to verify, should verify. It's an idiomatic pattern for all of our analyzes to be able to scatter verify calls under debug options, and have that locally catch problems in assert builds.

[anna]

In D109068#2978422, @reames wrote:

In D109068#2978419, @asbirlea wrote:

In D109068#2978402, @reames wrote:

In D109068#2977909, @asbirlea wrote:

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

FYI, this is not the sole issue. I manually added a call to MSSA->verifyMemorySSA() unconditionally to the end of the pass, and it did not catch this.

I'm sorry, I didn't fully parse this.
Adding MSSA->verifyMemorySSA() unconditionally to the end of the pass will not catch this. You need to enable EXPENSIVE_CHECKS (or uncomment the ifdefs inside verifyOrderingDominationAndDefUses for this case, there's more in another verify method). Part of the verification is disabled, even in debug build.
Or "by not sole issue" did you mean there's an additional issue not fixed by this patch?

I'd meant that a missing call to verify memory SSA was not the sole issue. Your explanation explains why an expensive checks build found this, but local testing (on an asserts build) did not.

However, please change this. Calling verifyMemorySSA should not change behavior based on EXPENSIVE_CHECKS!! EXPENSIVE_CHECKS can decide whether to call verify, or even change a "how hard" flag to the verify routine, but a manual call to verify, should verify. It's an idiomatic pattern for all of our analyzes to be able to scatter verify calls under debug options, and have that locally catch problems in assert builds.

I agree with Philip, so currently, unconditionally calling MSSA verification does some verification, but isn't clear "how much" and we don't have a way to call the more comprehensive one without enabling EXPENSIVE_CHECKS.
@asbirlea, I had a slightly different problem :) I assumed that if we build llvm without EXPENSIVE_CHECKS and commented out the macro where we set VerifyMemorySSA, we should get the *entire* verification for MemorySSA (https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/MemorySSA.cpp#L88). If there are additional verifications inside MSSA verifier functionality which is *separately* guarded under EXPENSIVE_CHECKS, that isn't intuitive.

Could we pls separate out into two different verification levels such as how we do for DT (Fast versus Full) and the developer places this the Full version under EXPENSIVE_CHECKS when we call the verification routines in passes. This also lets us know exactly what verification we're getting and we can just comment out EXPENSIVE_CHECKS for debugging bugs in specific passes. Example: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp#L609

[asbirlea]

In D109068#2979922, @anna wrote:

In D109068#2978422, @reames wrote:

In D109068#2978419, @asbirlea wrote:

In D109068#2978402, @reames wrote:

In D109068#2977909, @asbirlea wrote:

The reason the verification didn't trigger right after LoopDeletion is that it's under EXPENSIVE_CHECKS (in verifyOrderingDominationAndDefUses). MSSA is incorrect (without this change) after LoopDeletion.

FYI, this is not the sole issue. I manually added a call to MSSA->verifyMemorySSA() unconditionally to the end of the pass, and it did not catch this.

I'm sorry, I didn't fully parse this.
Adding MSSA->verifyMemorySSA() unconditionally to the end of the pass will not catch this. You need to enable EXPENSIVE_CHECKS (or uncomment the ifdefs inside verifyOrderingDominationAndDefUses for this case, there's more in another verify method). Part of the verification is disabled, even in debug build.
Or "by not sole issue" did you mean there's an additional issue not fixed by this patch?

I'd meant that a missing call to verify memory SSA was not the sole issue. Your explanation explains why an expensive checks build found this, but local testing (on an asserts build) did not.

However, please change this. Calling verifyMemorySSA should not change behavior based on EXPENSIVE_CHECKS!! EXPENSIVE_CHECKS can decide whether to call verify, or even change a "how hard" flag to the verify routine, but a manual call to verify, should verify. It's an idiomatic pattern for all of our analyzes to be able to scatter verify calls under debug options, and have that locally catch problems in assert builds.

I agree with Philip, so currently, unconditionally calling MSSA verification does some verification, but isn't clear "how much" and we don't have a way to call the more comprehensive one without enabling EXPENSIVE_CHECKS.
@asbirlea, I had a slightly different problem :) I assumed that if we build llvm without EXPENSIVE_CHECKS and commented out the macro where we set VerifyMemorySSA, we should get the *entire* verification for MemorySSA (https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/MemorySSA.cpp#L88). If there are additional verifications inside MSSA verifier functionality which is *separately* guarded under EXPENSIVE_CHECKS, that isn't intuitive.

Could we pls separate out into two different verification levels such as how we do for DT (Fast versus Full) and the developer places this the Full version under EXPENSIVE_CHECKS when we call the verification routines in passes. This also lets us know exactly what verification we're getting and we can just comment out EXPENSIVE_CHECKS for debugging bugs in specific passes. Example: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp#L609

Thank you for the suggestion, I'll send a patch for that.

[asbirlea]

Sent in https://reviews.llvm.org/rGb759381b7515 based on your suggestion. Much appreciated!

llvm/lib/Transforms/Utils/LoopUtils.cpp

if (auto *BI = dyn_cast<BranchInst>(Latch->getTerminator())) {
                                   MSSAU.get());
         return;
       }
 
       // Conditional latch/exit - note that latch can be shared by inner
       // and outer loop so the other target doesn't need to an exit
       if (L->isLoopExiting(Latch)) {
         // TODO: Generalize ConstantFoldTerminator so that it can be used
-        // here without invalidating LCSSA.  (Tricky case: header is an exit
-        // block of a preceeding sibling loop w/o dedicated exits.)
+        // here without invalidating LCSSA or MemorySSA.  (Tricky case for
+        // LCSSA: header is an exit block of a preceeding sibling loop w/o
+        // dedicated exits.)
         const unsigned ExitIdx = L->contains(BI->getSuccessor(0)) ? 1 : 0;
         BasicBlock *ExitBB = BI->getSuccessor(ExitIdx);
 
         DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
         Header->removePredecessor(Latch, true);
 
         IRBuilder<> Builder(BI);
         auto *NewBI = Builder.CreateBr(ExitBB);
         // Transfer the metadata to the new branch instruction (minus the
         // loop info since this is no longer a loop)
         NewBI->copyMetadata(*BI, {LLVMContext::MD_dbg,
                                   LLVMContext::MD_annotation});
 
         BI->eraseFromParent();
         DTU.applyUpdates({{DominatorTree::Delete, Latch, Header}});
+        if (MSSA)
+          MSSAU->applyUpdates({{DominatorTree::Delete, Latch, Header}}, DT);
         return;
       }
     }
 
     // General case.  By splitting the backedge, and then explicitly making it
     // unreachable we gracefully handle corner cases such as switch and invoke
     // termiantors.
     auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());

llvm/test/Transforms/LoopDeletion/bbi-59728.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -verify-memoryssa -passes='loop-mssa(loop-deletion,loop-simplifycfg)' -S | FileCheck %s
+
+; This is a case where we failed to update memory SSA correctly in
+; loop-deletion which escapes local verification, but causes a crash
+; in loop-simplifycfg.
+define void @func_45() {
+; CHECK-LABEL: @func_45(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY45:%.*]]
+; CHECK:       for.body45:
+; CHECK-NEXT:    store i32 433429641, i32* undef, align 1
+; CHECK-NEXT:    br label [[FOR_BODY45]]
+;
+entry:
+  br label %for.body45
+
+for.body45:                                       ; preds = %for.end72, %entry
+  br label %for.body48
+
+for.body48:                                       ; preds = %for.body48, %for.body45
+  store i32 433429641, i32* undef, align 1
+  br i1 undef, label %for.body48, label %for.end72
+
+for.end72:                                        ; preds = %for.body48
+  br label %for.body45
+}