Prevent crash when TurnSwitchRangeIntoICmp receives default unreachable destination

[swamulism]

Summary

TurnSwitchRangeIntoICmp crashes when given a switch with a default destination of unreachable
Addresses issue #53208
https://github.com/llvm/llvm-project/issues/53208

[aeubanks]

can you put the bug number (e.g. #12345) in the description?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5190

destination

5222

this comment makes it sound like at this point your comment is always true

5223

LLVM style is no braces for a one line if

llvm/test/Transforms/SimplifyCFG/switch-default-undef.ll

1

can you use llvm/utils/update_test_checks.py?

[hans]

Nice!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5222

Also, should it be "unreachable" rather than "undef"?

llvm/test/Transforms/SimplifyCFG/switch-default-undef.ll

1

Instead of creating a new file, could you add this as a test case to llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll instead?

9

In this switch, the default destination doesn't look unreachable. Is it made unreachable by some other transformation that happens before TurnSwitchRangeIntoICmp()? Can you make the test show the input that TurnSwitchRangeIntoICmp operates on directly?

[swamulism]

Updating D127712: Prevent crash when TurnSwitchRangeIntoICmp recieves default null dest

[swamulism]

llvm/test/Transforms/SimplifyCFG/switch-default-undef.ll

9

It is made unreachable by some other transformation.
Using the IR when the crash occurs in TurnSwitchRangeIntoICmp() as an input actually doesn't cause a crash (I assume it gets optimized out before we get here).
So, I guess there is some other combination of transformations that causes TurnSwitchRangeIntoICmp() to get a switch looking like this:

switch i8 %sw, label %unreachable [
  i8 10, label %group2
  i8 9, label %group2
]

[nikic]

It looks like you only uploaded the diff to the previous version, rather than the whole patch.

[swamulism]

Updating D127712: Prevent crash when TurnSwitchRangeIntoICmp receives default unreachable destination

[swamulism]

In D127712#3584496, @nikic wrote:

It looks like you only uploaded the diff to the previous version, rather than the whole patch.

Oops. Figured out how to use arcanist haha (I think)
Thanks for the catch

[swamulism]

Push whole patch

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5228

As this assert indicates, this case was supposed to be handled earlier already, namely by the ConstantFoldTerminator call. The reason it doesn't handle it is that https://github.com/llvm/llvm-project/blob/4c2bccfda3892ae13e97b6bfdbc99ec8cf5d095d/llvm/lib/Transforms/Utils/Local.cpp#L194-L198 will pick the unreachable block as the "only dest" and eliminate all unreachable cases. But that then leaves us with the actual only destination, which would get folded by a second call to ConstantFoldTerminator. Possibly the function should be improved to always find the non-unreachable dest.

But in any case, adding a conservative bailout here is reasonable, though the assertion message here is a bit outdated.

llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll

150 ↗

(On Diff #437078)

Please give this function a name (like pr53208_single_reachable_dest or something).

[swamulism]

update test fn name

[swamulism]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5228

It looks like this is optimized after anyways, but yeah ideally it shouldn't get to this point in the first place.

[nikic]

LG

[hans]

lgtm

Do you have commit access, or do you need someone to commit this for you?

[swamulism]

In D127712#3588623, @hans wrote:

lgtm

Do you have commit access, or do you need someone to commit this for you?

I need someone to commit this for me.
Thanks for reviewing!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (DTU) {
     SmallVector<DominatorTree::UpdateType, 2> Updates;
     Updates.push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
     if (!is_contained(successors(BB), OrigDefaultBlock))
       Updates.push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
     DTU->applyUpdates(Updates);
   }
 }
 
-/// Turn a switch with two reachable destinations into an integer range
-/// comparison and branch.
+/// Turn a switch into an integer range comparison and branch.
+/// Switches with more than 2 destinations are ignored.
+/// Switches with 1 destation are also ignored.
 bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(SwitchInst *SI,
                                              IRBuilder<> &Builder) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
   bool HasDefault =
       !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
 
   auto *BB = SI->getParent();
for (auto Case : SI->cases()) {
     if (!DestB)
       DestB = Dest;
     if (Dest == DestB) {
       CasesB.push_back(Case.getCaseValue());
       continue;
     }
     return false; // More than two destinations.
   }
+  // All destinations are the same and the default is undef
+  if (!DestB) {
+    return false;
+  }
 
   assert(DestA && DestB &&
          "Single-destination switch should have been folded.");
   assert(DestA != DestB);
   assert(DestB != SI->getDefaultDest());
   assert(!CasesB.empty() && "There must be non-default cases.");
   assert(!CasesA.empty() || HasDefault);
 
   // Figure out if one of the sets of cases form a contiguous range.
   SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr;
   BasicBlock *ContiguousDest = nullptr;

llvm/test/Transforms/SimplifyCFG/switch-default-undef.ll

+; RUN: opt -passes=simplifycfg"<switch-range-to-icmp>" -S %s | FileCheck %s
+
+; CHECK: define void @0(i8 %sw, i32* %p0) {
+; CHECK: group2:
+; CHECK: call void @bar(i32* %p0)
+; CHECK: ret void
+; CHECK: }
+define void @0(i8 %sw, i32* %p0) {
+  switch i8 %sw, label %group3 [
+    i8 0, label %group1
+    i8 1, label %group1
+    i8 2, label %group1
+    i8 3, label %group1
+    i8 11, label %group1
+    i8 12, label %group1
+    i8 13, label %group1
+    i8 7, label %group1
+    i8 17, label %group1
+    i8 14, label %group1
+    i8 15, label %group1
+    i8 4, label %group2
+    i8 5, label %group2
+    i8 6, label %group2
+    i8 8, label %group2
+    i8 9, label %group2
+    i8 10, label %group2
+  ]
+
+group1:
+  br label %exit
+
+group2:
+  br label %exit
+
+group3:
+  br label %exit
+
+exit:
+  %phi = phi i32* [ null, %group3 ], [ %p0, %group2 ], [ null, %group1 ]
+  call void @bar(i32* %phi)
+  ret void
+}
+
+; CHECK: declare void @bar(i32* nonnull dereferenceable(4))
+declare void @bar(i32* nonnull dereferenceable(4))
 No newline at end of file