[SimpleLoopUnswitch] Do not delete DT edge when a duplicate exists.

[asbirlea]

Summary

For the unswitched blocks that were split, there may be a duplicate edge
that was kept. Check this when updating the DominatorTree.
Resolves PR45355.

[asbirlea]

Nit in test.

[uabelho]

I don't really know this code but at least the fix avoids the crash I saw. Thanks!

[uabelho]

I've run quite a number of tests with this without problems.

[asbirlea]

While this solution does solve the problem, there's an underlying bug that this is hiding. I've talking with Chandler about this and I'll send a couple of patches that are aiming to fix the underlying problem instead.
Apologies for the delay in getting you a fix.

[uabelho]

In D77620#1985961, @asbirlea wrote:

While this solution does solve the problem, there's an underlying bug that this is hiding. I've talking with Chandler about this and I'll send a couple of patches that are aiming to fix the underlying problem instead.
Apologies for the delay in getting you a fix.

Sounds good!

[chandlerc]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

830

(mostly summarizing our video chat discussion for the list and so I don't forget it)

The raw llvm::successors API is somewhat inefficient (switches over the instruction op-code).... And no matter what, this ends up being quadratic in the weird edge case where we unswitch half of the edges. For each unswitched edge that we split we'll walk every not-unswitched edge here.

But all of this I think is unnecessary. We shouldn't ever be leaving edges from the *switch instruction* to a basic block that we are unswitching. The split case is only intended to cover when there are edges to the basic block from other parts of the loop.

The way you get here is really fun: it uses a basic block ending in unreachable. Such blocks are special cased above in this routine, but only for the *default* destination. That's how we end up with there still being an edge: its the default edge to an unreachable-terminated block where we unswitch a case edge to that block.

So I think we need to make the handling of unreachable-terminated blocks uniform between defaults and cases, even though we don't *need* to special case them for cases (because we can delete cases entirely). Otherwise we will keep having surprises where they behave differently here.

But to do that, I think we need to *narrow* the special case significantly: currently it just checks that the block is terminated by unreachable. I think it should *also* ensure that is the only instruction in the block. For all such exiting edges of the loop, we don't need to both unswitching them. Notably, the case edges should be cleaned up by SimplifyCFG by deleting them, so there is no real need to do anything here IMO.

So I think that leaves two steps here:

1. Narrow the special case to blocks containing *just* unreachable.
2. Apply in consistently to cases as well as the default destination.

I'm fine to do it in a single patch if it isn't too disruptive. Or we can do something vaguely similar to this patch as a temporary workaround that is easier to backport and then do #1 and #2 in to follow-up patches and remove the workaround.

[asbirlea]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

830

Thanks a lot for the summary, this is great to have in writing!

I sent out D78277 and D78279 last week as a replacement for this patch. My apologies for forgetting to update the discussion here.

[asbirlea]

Superseded by D78277 and D78279.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 ///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   // containers here, the API for applyUpdates takes an unordered list of
   // updates and requires them to not contain duplicates.
   SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
   for (auto *UnswitchedExitBB : UnswitchedExitBBs) {
     DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedExitBB});
     DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB});
   }
   for (auto SplitUnswitchedPair : SplitExitBBMap) {
+    // If the deleted edge was not duplicated in the switch, delete from the DT.
+    if (!llvm::is_contained(successors(ParentBB), SplitUnswitchedPair.first))
       DTUpdates.push_back({DT.Delete, ParentBB, SplitUnswitchedPair.first});
     DTUpdates.push_back({DT.Insert, OldPH, SplitUnswitchedPair.second});
   }
   DT.applyUpdates(DTUpdates);
 
   if (MSSAU) {
     MSSAU->applyUpdates(DTUpdates, DT);
     if (VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();

llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
 ; CHECK-NEXT:    br label %header
 
 loopexit:
   ret void
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret
 }
+
+; PR45355
+define void @test_unswitch_switch_with_duplicate_edge() {
+; CHECK-LABEL: @test_unswitch_switch_with_duplicate_edge()
+entry:
+  br label %lbl1
+
+lbl1.loopexit:                                    ; preds = %for.cond1
+  unreachable
+
+lbl1:                                             ; preds = %entry
+  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond1, %lbl1
+  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
+    i32 0, label %for.cond1
+    i32 5, label %UnifiedUnreachableBlock
+    i32 2, label %lbl1.loopexit
+  ]
+
+UnifiedUnreachableBlock:                          ; preds = %for.cond1, %for.cond1
+  unreachable
+
+; CHECK: lbl1:
+; CHECK-NEXT:  %cleanup.dest.slot.0 = select i1 undef, i32 5, i32 undef
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %lbl1.split [
+; CHECK-NEXT:    i32 5, label %UnifiedUnreachableBlock.split
+; CHECK-NEXT:    i32 2, label %lbl1.loopexit
+; CHECK-NEXT:  ]
+; CHECK-NEXT: lbl1.split:
+; CHECK-NEXT:  switch i32 %cleanup.dest.slot.0, label %UnifiedUnreachableBlock [
+; CHECK-NEXT:    i32 0, label %lbl1.split.split
+; CHECK-NEXT:  ]
+}