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!

llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "lower-switch"
 
 namespace {
+  struct IntRange {
+    int64_t Low, High;
+  };
+  // Return true iff R is covered by Ranges.
+  static bool IsInRanges(const IntRange &R,
+                         const std::vector<IntRange> &Ranges) {
+    // Note: Ranges must be sorted, non-overlapping and non-adjacent.
+
+    // Find the first range whose High field is >= R.High,
+    // then check if the Low field is <= R.Low. If so, we
+    // have a Range that covers R.
+    auto I = std::lower_bound(
+        Ranges.begin(), Ranges.end(), R,
+        [](const IntRange &A, const IntRange &B) { return A.High < B.High; });
+    return I != Ranges.end() && I->Low <= R.Low;
+  }
+
   /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
   /// instructions.
   class LowerSwitch : public FunctionPass {
   public:
     static char ID; // Pass identification, replacement for typeid
     LowerSwitch() : FunctionPass(ID) {
       initializeLowerSwitchPass(*PassRegistry::getPassRegistry());
     } 
public:
     typedef std::vector<CaseRange> CaseVector;
     typedef std::vector<CaseRange>::iterator CaseItr;
   private:
     void processSwitchInst(SwitchInst *SI);
 
     BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
                               ConstantInt *LowerBound, ConstantInt *UpperBound,
                               Value *Val, BasicBlock *Predecessor,
-                              BasicBlock *OrigBlock, BasicBlock *Default);
+                              BasicBlock *OrigBlock, BasicBlock *Default,
+                              const std::vector<IntRange> &UnreachableRanges);
     BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock,
                              BasicBlock *Default);
     unsigned Clusterify(CaseVector &Cases, SwitchInst *SI);
   };
 
   /// The comparison function for sorting the switch case values in the vector.
   /// WARNING: Case ranges should be disjoint!
   struct CaseCmp {
static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
   }
 }
 
 // switchConvert - Convert the switch statement into a binary lookup of
 // the case values. The function recursively builds this tree.
 // LowerBound and UpperBound are used to keep track of the bounds for Val
 // that have already been checked by a block emitted by one of the previous
 // calls to switchConvert in the call stack.
-BasicBlock *LowerSwitch::switchConvert(CaseItr Begin, CaseItr End,
-                                       ConstantInt *LowerBound,
-                                       ConstantInt *UpperBound, Value *Val,
-                                       BasicBlock *Predecessor,
-                                       BasicBlock *OrigBlock,
-                                       BasicBlock *Default) {
+BasicBlock *
+LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
+                           BasicBlock *Predecessor, BasicBlock *OrigBlock,
+                           BasicBlock *Default,
+                           const std::vector<IntRange> &UnreachableRanges) {
   unsigned Size = End - Begin;
 
   if (Size == 1) {
     // Check if the Case Range is perfectly squeezed in between
     // already checked Upper and Lower bounds. If it is then we can avoid
     // emitting the code that checks if the value actually falls in the range
     // because the bounds already tell us so.
     if (Begin->Low == LowerBound && Begin->High == UpperBound) {
DEBUG(dbgs() << "Pivot ==> "
                << cast<ConstantInt>(Pivot.Low)->getValue()
                << " -" << cast<ConstantInt>(Pivot.High)->getValue() << "\n");
 
   // NewLowerBound here should never be the integer minimal value.
   // This is because it is computed from a case range that is never
   // the smallest, so there is always a case range that has at least
   // a smaller value.
   ConstantInt *NewLowerBound = cast<ConstantInt>(Pivot.Low);
-  ConstantInt *NewUpperBound;
 
-  // If we don't have a Default block then it means that we can never
-  // have a value outside of a case range, so set the UpperBound to the highest
-  // value in the LHS part of the case ranges.
-  if (Default != nullptr) {
-    // Because NewLowerBound is never the smallest representable integer
-    // it is safe here to subtract one.
-    NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
+  ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
                                                 NewLowerBound->getValue() - 1);
-  } else {
-    CaseItr LastLHS = LHS.begin() + LHS.size() - 1;
-    NewUpperBound = cast<ConstantInt>(LastLHS->High);
+
+  if (!UnreachableRanges.empty()) {
+    // Check if the gap between LHS's highest and NewLowerBound is unreachable.
+    int64_t GapLow = cast<ConstantInt>(LHS.back().High)->getSExtValue() + 1;
+    int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
+    IntRange Gap = { GapLow, GapHigh };
+    if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
+      NewUpperBound = cast<ConstantInt>(LHS.back().High);
   }
 
   DEBUG(dbgs() << "LHS Bounds ==> ";
         if (LowerBound) {
           dbgs() << cast<ConstantInt>(LowerBound)->getSExtValue();
         } else {
           dbgs() << "NONE";
         }
LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
   Function* F = OrigBlock->getParent();
   BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
 
   ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT,
                                 Val, Pivot.Low, "Pivot");
 
   BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
                                       NewUpperBound, Val, NewNode, OrigBlock,
-                                      Default);
+                                      Default, UnreachableRanges);
   BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
                                       UpperBound, Val, NewNode, OrigBlock,
-                                      Default);
+                                      Default, UnreachableRanges);
 
   Function::iterator FI = OrigBlock;
   F->getBasicBlockList().insert(++FI, NewNode);
   NewNode->getInstList().push_back(Comp);
 
   BranchInst::Create(LBranch, RBranch, Comp, NewNode);
   return NewNode;
 }

 //
 void LowerSwitch::processSwitchInst(SwitchInst *SI) {
   BasicBlock *CurBlock = SI->getParent();
   BasicBlock *OrigBlock = CurBlock;
   Function *F = CurBlock->getParent();
   Value *Val = SI->getCondition();  // The value we are switching on...
   BasicBlock* Default = SI->getDefaultDest();
 
-  // If there is only the default destination, don't bother with the code below.
+  // If there is only the default destination, just branch.
   if (!SI->getNumCases()) {
-    BranchInst::Create(SI->getDefaultDest(), CurBlock);
-    CurBlock->getInstList().erase(SI);
+    BranchInst::Create(Default, CurBlock);
+    SI->eraseFromParent();
+    return;
+  }
+
+  // Prepare cases vector.
+  CaseVector Cases;
+  unsigned numCmps = Clusterify(Cases, SI);
+  DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
+               << ". Total compares: " << numCmps << "\n");
+  DEBUG(dbgs() << "Cases: " << Cases << "\n");
+  (void)numCmps;
+
+  ConstantInt *LowerBound = nullptr;
+  ConstantInt *UpperBound = nullptr;
+  std::vector<IntRange> UnreachableRanges;
+
+  if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
+    // Make the bounds tightly fitted around the case value range, becase we
+    // know that the value passed to the switch must be exactly one of the case
+    // values.
+    assert(!Cases.empty());
+    LowerBound = cast<ConstantInt>(Cases.front().Low);
+    UpperBound = cast<ConstantInt>(Cases.back().High);
+
+    DenseMap<BasicBlock *, unsigned> Popularity;
+    unsigned MaxPop = 0;
+    BasicBlock *PopSucc = nullptr;
+
+    IntRange R = { INT64_MIN, INT64_MAX };
+    UnreachableRanges.push_back(R);
+    for (const auto &I : Cases) {
+      int64_t Low = cast<ConstantInt>(I.Low)->getSExtValue();
+      int64_t High = cast<ConstantInt>(I.High)->getSExtValue();
+
+      IntRange &LastRange = UnreachableRanges.back();
+      if (LastRange.Low == Low) {
+        // There is nothing left of the previous range.
+        UnreachableRanges.pop_back();
+      } else {
+        // Terminate the previous range.
+        assert(Low > LastRange.Low);
+        LastRange.High = Low - 1;
+      }
+      if (High != INT64_MAX) {
+        IntRange R = { High + 1, INT64_MAX };
+        UnreachableRanges.push_back(R);
+      }
+
+      // Count popularity.
+      int64_t N = High - Low + 1;
+      unsigned &Pop = Popularity[I.BB];
+      if ((Pop += N) > MaxPop) {
+        MaxPop = Pop;
+        PopSucc = I.BB;
+      }
+    }
+#ifndef NDEBUG
+    /* UnreachableRanges should be sorted and the ranges non-adjacent. */
+    for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
+         I != E; ++I) {
+      assert(I->Low <= I->High);
+      auto Next = I + 1;
+      if (Next != E) {
+        assert(Next->Low > I->High);
+      }
+    }
+#endif
+
+    // Use the most popular block as the new default, reducing the number of
+    // cases.
+    assert(MaxPop > 0 && PopSucc);
+    Default = PopSucc;
+    for (CaseItr I = Cases.begin(); I != Cases.end();) {
+      if (I->BB == PopSucc)
+        I = Cases.erase(I);
+      else
+        ++I;
+    }
+
+    // If there are no cases left, just branch.
+    if (Cases.empty()) {
+      BranchInst::Create(Default, CurBlock);
+      SI->eraseFromParent();
       return;
     }
+  }
 
-  const bool DefaultIsUnreachable =
-      Default->size() == 1 && isa<UnreachableInst>(Default->getTerminator());
   // 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);
-
-    BranchInst::Create(Default, NewDefault);
-  }
+  BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
+
   // If there is an entry in any PHI nodes for the default edge, make sure
   // to update them as well.
   for (BasicBlock::iterator I = Default->begin(); isa<PHINode>(I); ++I) {
     PHINode *PN = cast<PHINode>(I);
     int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
     assert(BlockIdx != -1 && "Switch didn't go to this successor??");
     PN->setIncomingBlock((unsigned)BlockIdx, NewDefault);
   }
 
-  // Prepare cases vector.
-  CaseVector Cases;
-  unsigned numCmps = Clusterify(Cases, SI);
-
-  DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
-               << ". Total compares: " << numCmps << "\n");
-  DEBUG(dbgs() << "Cases: " << Cases << "\n");
-  (void)numCmps;
-  
-  ConstantInt *UpperBound = nullptr;
-  ConstantInt *LowerBound = nullptr;
-
-  // Optimize the condition where Default is an unreachable block. In this case
-  // we can make the bounds tightly fitted around the case value ranges,
-  // because we know that the value passed to the switch should always be
-  // exactly one of the case values.
-  if (DefaultIsUnreachable) {
-    CaseItr LastCase = Cases.begin() + Cases.size() - 1;
-    UpperBound = cast<ConstantInt>(LastCase->High);
-    LowerBound = cast<ConstantInt>(Cases.begin()->Low);
-  }
   BasicBlock *SwitchBlock =
       switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
-                    OrigBlock, OrigBlock, NewDefault);
+                    OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
 
   // 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);
 }

llvm/trunk/test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll

 ; RUN: opt < %s -lowerswitch -S | FileCheck %s
-; CHECK-NOT: {{.*}}icmp eq{{.*}}
+;
+; The switch is lowered with a single icmp.
+; CHECK: icmp
+; CHECK-NOT: icmp
 ;
 ;int foo(int a) {
 ;
 ;  switch (a) {
 ;  case 0:
 ;    return 10;
 ;  case 1:
 ;    return 3;
 ;  default:
 ;    __builtin_unreachable();
 ;  }
 ;
 ;}
 
-define i32 @foo(i32 %a) nounwind ssp uwtable {
+define i32 @foo(i32 %a) {
   %1 = alloca i32, align 4
   %2 = alloca i32, align 4
   store i32 %a, i32* %2, align 4
   %3 = load i32* %2, align 4
   switch i32 %3, label %6 [
     i32 0, label %4
     i32 1, label %5
   ]

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

+; RUN: opt %s -lowerswitch -S | FileCheck %s
+
+define void @foo(i32 %x, i32* %p) {
+; Cases 2 and 4 are removed and become the new default case.
+; It is now enough to use two icmps to lower the switch.
+;
+; CHECK-LABEL: @foo
+; CHECK:       icmp slt i32 %x, 5
+; CHECK:       icmp eq i32 %x, 1
+; CHECK-NOT:   icmp
+;
+entry:
+  switch i32 %x, label %default [
+    i32 1, label %bb0
+    i32 2, label %popular
+    i32 4, label %popular
+    i32 5, label %bb1
+  ]
+bb0:
+  store i32 0, i32* %p
+  br label %exit
+bb1:
+  store i32 1, i32* %p
+  br label %exit
+popular:
+  store i32 2, i32* %p
+  br label %exit
+exit:
+  ret void
+default:
+  unreachable
+}
+
+define void @unreachable_gap(i64 %x, i32* %p) {
+; Cases 6 and INT64_MAX become the new default, but we still exploit the fact
+; that 3-4 is unreachable, so four icmps is enough.
+
+; CHECK-LABEL: @unreachable_gap
+; CHECK:       icmp slt i64 %x, 2
+; CHECK:       icmp slt i64 %x, 5
+; CHECK:       icmp eq  i64 %x, 5
+; CHECK:       icmp slt i64 %x, 1
+; CHECK-NOT:   icmp
+
+entry:
+  switch i64 %x, label %default [
+    i64 -9223372036854775808, label %bb0
+    i64 1, label %bb1
+    i64 2, label %bb2
+    i64 5, label %bb3
+    i64 6, label %bb4
+    i64 9223372036854775807, 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
+}
+
+
+
+define void @nocases(i32 %x, i32* %p) {
+; Don't fall over when there are no cases.
+;
+; CHECK-LABEL: @nocases
+; CHECK-LABEL: entry
+; CHECK-NEXT:  br label %default
+;
+entry:
+  switch i32 %x, label %default [
+  ]
+default:
+  unreachable
+}
+
+define void @nocasesleft(i32 %x, i32* %p) {
+; Cases 2 and 4 are removed and we are left with no cases.
+;
+; CHECK-LABEL: @nocasesleft
+; CHECK-LABEL: entry
+; CHECK-NEXT:  br label %popular
+;
+entry:
+  switch i32 %x, label %default [
+    i32 2, label %popular
+    i32 4, label %popular
+  ]
+popular:
+  store i32 2, i32* %p
+  br label %exit
+exit:
+  ret void
+default:
+  unreachable
+}