LowerSwitch: replace unreachable default with popular case destination

[hans]

Summary

SimplifyCFG currently does this transformation, but I'm planning to remove that (see [1]) in order to be able to exploit unreachable defaults in lowering. By moving it here, we make sure that we don't lose functionality for IR going through SImplifyCFG -> LowerSwitch.

Please take a look.

1. http://reviews.llvm.org/D6471

[hans]

Ping?

[hans]

Ping?

[kariddi]

Sorry for the delay! I didn't catch this conversation :-)

The idea itself of this optimization is good and ideally sounds promising for the case where there are many different, non-contiguous switch cases all pointing to the same block, but I'm not sure this is worth it overall.

The main problem is that the presence of a default block confuses the UpperBound and LowerBound computations , that cannot rely on skipping gaps between ranges of switch values anymore, which is a good optimization if the default block is absent.

Your test case is an example of code that gets worse in this case with the patch that without.

I guess is a matter of deciding if the case of non-contiguous switch cases pointing to the same block is a common case or not.

[kariddi]

I'm attaching the graphs of the test case lowered through lowerswitch with and without the patch to give context to what I mean:

[hans]

Thanks for your comments!

I'll see if I can rework the patch to be smarter about when to replace the unreachable default. (Probably not until after the holidays though.)

However, SimplifyCFG already does this transformation (I'm trying to remove it to be able to exploit unreachable switches in codegen). Does SimplifyCFG not normally run fore LowerSwitch?

[kariddi]

Thanks for working on this :-)

Usually LowerSwitch runs pretty late in the pipeline, in preparation for CodeGen.

[hans]

The main problem is that the presence of a default block confuses the UpperBound and LowerBound computations , that cannot rely on skipping gaps between ranges of switch values anymore, which is a good optimization if the default block is absent.

Your test case is an example of code that gets worse in this case with the patch that without.

I think the problem was just that my patch prevented us from setting LowerBound and UpperBound. We should still set them even if the unreachable default gets replaced with a reachable destination. With that, I think there is no trade-off here - replacing the unreachable default is always profitable or neutral.

Thanks for catching that my test case was an example of where things got worse; that's embarrassing :) I've added a new test that benefits both from replacing the default and having UpperBound and LowerBound set.

Usually LowerSwitch runs pretty late in the pipeline, in preparation for CodeGen.

Looking forward to getting this transformation out of SimplifyCFG so LowerSwitch can benefit, then :)

[hans]

Ping?

[hans]

Updating the patch to handle the situation where all cases get moved to the default, and simplifying the code a little.

[kariddi]

Hi Hans, thanks for your work on this! I'm looking into your patch now :-)

Marcello

2015-01-15 17:13 GMT-08:00 Hans Wennborg <[e-mail]>:

Updating the patch to handle the situation where all cases get moved to
the default, and simplifying the code a little.

http://reviews.llvm.org/D6697

Files:

lib/Transforms/Utils/LowerSwitch.cpp
test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll
test/Transforms/LowerSwitch/fold-popular-case-to-unreachable-default.ll

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[kariddi]

I still see some potential drawbacks on some CFGs.

Lets take this example, derived from your original test:

test.ll838 BDownload

In this case there is a gap between the values of the cases.
Your Min/MaxCase approach works fine on the edges of the range of the cases, but doesn't do anything in the case there is a gap between cases.
If there is a gap between the cases the fact that there is no Default block still gives us the possibility to avoid having to check if the value falls into the gap or not.
Basically we are still losing the boundary information on the bounds that fall on gaps.

Here are the CFG of the example with and without your patch.

Maybe there is a way to actually also check for the boundaries on the gaps and integrating them in the algorithm.
I have to think about it, maybe we can also speak about it on IRC if you want :-)

with_patch.pdf25 KBDownload

without_patch.pdf23 KBDownload

[hans]

Ah, I see what you mean. I didn't notice that the code was exploiting that.

I guess we could try to come up with a heuristic for when replacing the unreachable default is profitable even though we can't exploit the unreachable gaps. For example, if we can remove half or more of the case clusters, it's probably profitable.

I'm not sure how to proceed here though. My patch is really just preserving current functionality, but moving it out of SimplifyCFG (and now with the bonus of allowing this code to set Lower/UpperBound.)

If you think it's better for LowerSwitch to not do this transformation, I'm fine with that too. Or we could try to come up with a heuristic for when it's more profitable than exploiting the unreachable gaps.

[kariddi]

I think there is probably a way to make it such that we take advantage of your work.

Originally, before your algorithm runs the switch case ranges have naturally holes that if the default is unreachable are unreachable as well and can be used as bounds.
Basically your algorithm detects that the Default is unreachable and adds additional holes by removing the cases that point to the most common successor.
Now though you introduce an ambiguity. Some of the holes are actually unreachable (which are the original "holes" before your algorithm run) , but some other are not (which are the ones you introduced) , but we cannot differentiate between the two.

If we instead , before running your algorithm, we collect the ranges that are true unreachable gaps and use this information in the lowering algorithm to make the best assumptions between upper and lower bounds I think we can reach the optimum.

[hans]

If we instead , before running your algorithm, we collect the ranges that are true unreachable gaps and use this information in the lowering algorithm to make the best assumptions between upper and lower bounds I think we can reach the optimum.

That sounds like a good idea. I've uploaded a patch that does this. It might need some polish, but please take a look and let me know if you think it's on the right track.

[kariddi]

Yeah, that sounds like it!
This is exactly what I meant :)

[hans]

Yeah, that sounds like it!
This is exactly what I meant :)

Great! I've tidied up the patch a little, and made sure to use signed integers for IntRange since we're treating the case values as signed in the rest of the code.

Please take a look when you have time.

[kariddi]

Hi Hans!
Sorry for the delay. Your patch is very good. Thank you!

lib/Transforms/Utils/LowerSwitch.cpp

void LowerSwitch::processSwitchInst(SwitchInst *SI) {
 
   // If there is only the default destination, don't bother with the code below.
   if (!SI->getNumCases()) {
     BranchInst::Create(SI->getDefaultDest(), CurBlock);
     CurBlock->getInstList().erase(SI);
     return;
   }
 
-  const bool DefaultIsUnreachable =
-      Default->size() == 1 && isa<UnreachableInst>(Default->getTerminator());
+  bool DefaultIsUnreachable =
+      isa<UnreachableInst>(Default->getFirstNonPHIOrDbg());
+
+  if (DefaultIsUnreachable) {
+    DenseMap<BasicBlock *, unsigned> Popularity;
+    unsigned MaxPop = 0;
+    BasicBlock *MaxBB = nullptr;
+    for (auto I : SI->cases()) {
+      BasicBlock *BB = I.getCaseSuccessor();
+      if (++Popularity[BB] > MaxPop) {
+        MaxPop = Popularity[BB];
+        MaxBB = BB;
+      }
+    }
+    if (MaxPop > 1) {
+      // If some block is extra popular, use that as the default result,
+      // reducing the number of cases.
+      Default = MaxBB;
+      DefaultIsUnreachable = false;
+      for (auto I = SI->case_begin(); I != SI->case_end();) {
+        if (I.getCaseSuccessor() == MaxBB)
+          SI->removeCase(I);
+        else
+          ++I;
+      }
+    }
+  }
+
   // Create a new, empty default block so that the new hierarchy of
   // if-then statements go to this and the PHI nodes are happy.
   // if the default block is set as an unreachable we avoid creating one
   // because will never be a valid target.
   BasicBlock *NewDefault = nullptr;
   if (!DefaultIsUnreachable) {
     NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
     F->getBasicBlockList().insert(Default, NewDefault);
void LowerSwitch::processSwitchInst(SwitchInst *SI) {
   BasicBlock *SwitchBlock =
       switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
                     OrigBlock, OrigBlock, NewDefault);
 
   // Branch to our shiny new if-then stuff...
   BranchInst::Create(SwitchBlock, OrigBlock);
 
   // We are now done with the switch instruction, delete it.
+  BasicBlock *OldDefault = SI->getDefaultDest();
   CurBlock->getInstList().erase(SI);
 
-  pred_iterator PI = pred_begin(Default), E = pred_end(Default);
-  // If the Default block has no more predecessors just remove it
-  if (PI == E) {
-    DeleteDeadBlock(Default);
-  }
+  // If the Default block has no more predecessors just remove it.
+  if (pred_begin(OldDefault) == pred_end(OldDefault))
+    DeleteDeadBlock(OldDefault);
 }

test/Transforms/LowerSwitch/fold-popular-case-to-unreachable-default.ll

+; RUN: opt %s -lowerswitch -S | FileCheck %s
+
+; An unreachabel default is replaced with a popular case label.
+
+define void @foo(i32 %x, i32* %p) {
+; CHECK-LABEL: @foo
+; CHECK:       icmp {{[a-z]+}} i32 %x, 3
+; CHECK-NOT:   icmp {{[a-z]+}} i32 %x, 4
+; CHECK-NOT:   icmp {{[a-z]+}} i32 %x, 5
+; CHECK-LABEL: NewDefault:
+; CHECK-NEXT:  br label %bb4
+; CHECK-NOT: default:
+; CEHCK-NOT: unreachable
+
+entry:
+  switch i32 %x, label %default [
+    i32 0, label %bb0
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
+    i32 4, label %bb4
+    i32 5, label %bb4
+  ]
+bb0:
+  store i32 0, i32* %p
+  br label %exit
+bb1:
+  store i32 1, i32* %p
+  br label %exit
+bb2:
+  store i32 2, i32* %p
+  br label %exit
+bb3:
+  store i32 3, i32* %p
+  br label %exit
+bb4:
+  store i32 4, i32* %p
+  br label %exit
+exit:
+  ret void
+default:
+  unreachable
+}