SimplifyCFG: don't remove unreachable defaults from switch instructions; exploit them instead!

[hans]

Summary

This patch actually does a number of related things. I'm happy to split it up if it makes reviewing easier:

1. Make SimplifyCFG stop removing unreachable defaults so they can be exploited by other transformations.

2. Omit range checks in switch-to-lookup table formation if the default is unreachable. This saves 64 kB off a Clang bootstrap on 64-bit Linux. No effect on Chromium unfortunately.

3. Make ConstantFoldTerminator() work when faced with unreachable default.

4. Make TurnSwitchRangeIntoICmp() work with unreachable default. This also makes us handle some cases we'd previously get wrong, see the unreachable2 test.

Please take a look!

[majnemer]

I think it would be nice to split the patch into middle-end and backend pieces.

[hans]

I think it would be nice to split the patch into middle-end and backend pieces.

I've uploaded the backend part here: http://reviews.llvm.org/D6510

[hans]

I committed the tests that were checking existing functionality in r223395 and r223396 to reduce the size of this patch a little.

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3228 ↗

(On Diff #16955)

!ContiguousCases->empty()

3247 ↗

(On Diff #16955)

I'd go with UINT32_MAX to match the casts bellow.

4202 ↗

(On Diff #16955)

/*DontDeleteUselessPHIs=*/true

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

3228 ↗

(On Diff #16955)

Done.

3247 ↗

(On Diff #16955)

Done.

4202 ↗

(On Diff #16955)

Done.

[hans]

Addressing David's patches.

[resistor]

Can you update LowerSwitch.cpp to incorporate this optimization? Otherwise targets that rely on it are losing this functionality.

—Owen

[hans]

In D6471#14, @resistor wrote:

Can you update LowerSwitch.cpp to incorporate this optimization? Otherwise targets that rely on it are losing this functionality.

It seems LowerSwitch.cpp is already set up to exploit unreachable defaults, see the test in test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll

I guess it's a choice of whether that's important, or if moving popular cases into the default is better. If it's the latter I'm happy to implement it.

[hans]

I've uploaded a patch for this here: http://reviews.llvm.org/D6697

• Hans

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

if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
            i != e; ++i)
         if (i.getCaseSuccessor() == BB) {
           BB->removePredecessor(SI->getParent());
           SI->removeCase(i);
           --i; --e;
           Changed = true;
         }
-      // If the default value is unreachable, figure out the most popular
-      // destination and make it the default.
-      if (SI->getDefaultDest() == BB) {
-        std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
-        for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
-             i != e; ++i) {
-          std::pair<unsigned, unsigned> &entry =
-              Popularity[i.getCaseSuccessor()];
-          if (entry.first == 0) {
-            entry.first = 1;
-            entry.second = i.getCaseIndex();
-          } else {
-            entry.first++;
-          }
-        }
-
-        // Find the most popular block.
-        unsigned MaxPop = 0;
-        unsigned MaxIndex = 0;
-        BasicBlock *MaxBlock = nullptr;
-        for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
-             I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
-          if (I->second.first > MaxPop ||
-              (I->second.first == MaxPop && MaxIndex > I->second.second)) {
-            MaxPop = I->second.first;
-            MaxIndex = I->second.second;
-            MaxBlock = I->first;
-          }
-        }
-        if (MaxBlock) {
-          // Make this the new default, allowing us to delete any explicit
-          // edges to it.
-          SI->setDefaultDest(MaxBlock);
-          Changed = true;
-
-          // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
-          // it.
-          if (isa<PHINode>(MaxBlock->begin()))
-            for (unsigned i = 0; i != MaxPop-1; ++i)
-              MaxBlock->removePredecessor(SI->getParent());
-
-          for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
-               i != e; ++i)
-            if (i.getCaseSuccessor() == MaxBlock) {
-              SI->removeCase(i);
-              --i; --e;
-            }
-        }
-      }
     } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
       if (II->getUnwindDest() == BB) {
         // Convert the invoke to a call instruction.  This would be a good
         // place to note that the call does not throw though.
         BranchInst *BI = Builder.CreateBr(II->getNormalDest());
         II->removeFromParent();   // Take out of symbol table
 
         // Insert the call now...
if (pred_empty(BB) &&
     // We know there are no successors, so just nuke the block.
     BB->eraseFromParent();
     return true;
   }
 
   return Changed;
 }
 
-/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
-/// integer range comparison into a sub, an icmp and a branch.
+static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {
+  assert(Cases.size() >= 1);
+
+  array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
+  for (size_t I = 1, E = Cases.size(); I != E; ++I) {
+    if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1)
+      return false;
+  }
+  return true;
+}
+
+/// Turn a switch with two reachable destinations into an integer range
+/// comparison and branch.
 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
-  // Make sure all cases point to the same destination and gather the values.
-  SmallVector<ConstantInt *, 16> Cases;
-  SwitchInst::CaseIt I = SI->case_begin();
-  Cases.push_back(I.getCaseValue());
-  SwitchInst::CaseIt PrevI = I++;
-  for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) {
-    if (PrevI.getCaseSuccessor() != I.getCaseSuccessor())
-      return false;
-    Cases.push_back(I.getCaseValue());
+  bool HasDefault =
+      !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
+
+  // Partition the cases into two sets with different destinations.
+  BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
+  BasicBlock *DestB = nullptr;
+  SmallVector <ConstantInt *, 16> CasesA;
+  SmallVector <ConstantInt *, 16> CasesB;
+
+  for (SwitchInst::CaseIt I : SI->cases()) {
+    BasicBlock *Dest = I.getCaseSuccessor();
+    if (!DestA) DestA = Dest;
+    if (Dest == DestA) {
+      CasesA.push_back(I.getCaseValue());
+      continue;
+    }
+    if (!DestB) DestB = Dest;
+    if (Dest == DestB) {
+      CasesB.push_back(I.getCaseValue());
+      continue;
+    }
+    return false;  // More than two destinations.
   }
-  assert(Cases.size() == SI->getNumCases() && "Not all cases gathered");
 
-  // Sort the case values, then check if they form a range we can transform.
-  array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
-  for (unsigned I = 1, E = Cases.size(); I != E; ++I) {
-    if (Cases[I-1]->getValue() != Cases[I]->getValue()+1)
-      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;
+  BasicBlock *OtherDest = nullptr;
+  if (!CasesA.empty() && CasesAreContiguous(CasesA)) {
+    ContiguousCases = &CasesA;
+    ContiguousDest = DestA;
+    OtherDest = DestB;
+  } else if (CasesAreContiguous(CasesB)) {
+    ContiguousCases = &CasesB;
+    ContiguousDest = DestB;
+    OtherDest = DestA;
+  } else
 
-  Constant *Offset = ConstantExpr::getNeg(Cases.back());
-  Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases());
+  // Start building the compare and branch.
+
+  Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back());
+  Constant *NumCases = ConstantInt::get(Offset->getType(), ContiguousCases->size());
 
   Value *Sub = SI->getCondition();
   if (!Offset->isNullValue())
-    Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off");
+    Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off");
+
   Value *Cmp;
   // If NumCases overflowed, then all possible values jump to the successor.
-  if (NumCases->isNullValue() && SI->getNumCases() != 0)
+  if (NumCases->isNullValue() && !ContiguousCases->empty())
     Cmp = ConstantInt::getTrue(SI->getContext());
   else
     Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
-  BranchInst *NewBI = Builder.CreateCondBr(
-      Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest());
+  BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest);
 
   // Update weight for the newly-created conditional branch.
+  if (HasBranchWeights(SI)) {
     SmallVector<uint64_t, 8> Weights;
-  bool HasWeights = HasBranchWeights(SI);
-  if (HasWeights) {
     GetBranchWeights(SI, Weights);
     if (Weights.size() == 1 + SI->getNumCases()) {
-      // Combine all weights for the cases to be the true weight of NewBI.
-      // We assume that the sum of all weights for a Terminator can fit into 32
-      // bits.
-      uint32_t NewTrueWeight = 0;
-      for (unsigned I = 1, E = Weights.size(); I != E; ++I)
-        NewTrueWeight += (uint32_t)Weights[I];
+      uint64_t TrueWeight = 0;
+      uint64_t FalseWeight = 0;
+      for (size_t I = 0, E = Weights.size(); I != E; ++I) {
+        if (SI->getSuccessor(I) == ContiguousDest)
+          TrueWeight += Weights[I];
+        else
+          FalseWeight += Weights[I];
+      }
+      while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
+        TrueWeight /= 2;
+        FalseWeight /= 2;
+      }
       NewBI->setMetadata(LLVMContext::MD_prof,
-                         MDBuilder(SI->getContext()).
-                         createBranchWeights(NewTrueWeight,
-                                             (uint32_t)Weights[0]));
+                         MDBuilder(SI->getContext()).createBranchWeights(
+                             (uint32_t)TrueWeight, (uint32_t)FalseWeight));
     }
   }
 
-  // Prune obsolete incoming values off the successor's PHI nodes.
-  for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin();
-       isa<PHINode>(BBI); ++BBI) {
-    for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I)
+  // Prune obsolete incoming values off the successors' PHI nodes.
+  for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) {
+    unsigned PreviousEdges = ContiguousCases->size();
+    if (ContiguousDest == SI->getDefaultDest()) ++PreviousEdges;
+    for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
       cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
   }
+  for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) {
+    unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size();
+    if (OtherDest == SI->getDefaultDest()) ++PreviousEdges;
+    for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
+      cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
+  }
+
+  // Drop the switch.
   SI->eraseFromParent();
 
   return true;
 }
 
 /// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
 /// and use it to remove dead cases.
 static bool EliminateDeadSwitchCases(SwitchInst *SI, const DataLayout *DL,

llvm/trunk/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

 default:
         ret i32 1
 U:
         unreachable
 T:
         ret i32 2
 }
 
-; PR9450
-define i32 @test4(i32 %v, i32 %w) {
-; CHECK: entry:
-; CHECK-NEXT:  switch i32 %v, label %T [
-; CHECK-NEXT:    i32 3, label %V
-; CHECK-NEXT:    i32 2, label %U
-; CHECK-NEXT:  ]
-
-entry:
-        br label %SWITCH
-V:
-        ret i32 7
-SWITCH:
-        switch i32 %v, label %default [
-                 i32 1, label %T
-                 i32 2, label %U
-                 i32 3, label %V
-        ]
-default:
-        unreachable
-U:
-        ret i32 %w
-T:
-        ret i32 2
-}
-
 
 ;; We can either convert the following control-flow to a select or remove the
 ;; unreachable control flow because of the undef store of null. Make sure we do
 ;; the latter.
 
 define void @test5(i1 %cond, i8* %ptr) {
 
 ; CHECK-LABEL: test5

llvm/trunk/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 ; CHECK: @switch.table3 = private unnamed_addr constant [4 x i32] [i32 42, i32 9, i32 88, i32 5]
 
 ; The table for @large.
 ; CHECK: @switch.table4 = private unnamed_addr constant [199 x i32] [i32 1, i32 4, i32 9,
 
 ; The table for @cprop
 ; CHECK: @switch.table5 = private unnamed_addr constant [7 x i32] [i32 5, i32 42, i32 126, i32 -452, i32 128, i32 6, i32 7]
 
-; The table for @unreachable
-; CHECK: @switch.table6 = private unnamed_addr constant [5 x i32] [i32 0, i32 0, i32 0, i32 1, i32 -1]
+; The table for @unreachable_case
+; CHECK: @switch.table6 = private unnamed_addr constant [9 x i32] [i32 0, i32 0, i32 0, i32 2, i32 -1, i32 1, i32 1, i32 1, i32 1]
 
 ; A simple int-to-int selection switch.
 ; It is dense enough to be replaced by table lookup.
 ; The result is directly by a ret from an otherwise empty bb,
 ; so we return early, directly from the lookup bb.
 
 define i32 @f(i32 %c) {
 entry:
return:
   %retval.0 = phi i32 [ 123, %sw.default ], [ %select, %sw.bb3 ], [ %sub, %sw.bb2 ], [ 42, %sw.bb1 ], [ 5, %entry ]
   ret i32 %retval.0
 
 ; CHECK-LABEL: @cprop(
 ; CHECK: switch.lookup:
 ; CHECK: %switch.gep = getelementptr inbounds [7 x i32]* @switch.table5, i32 0, i32 %switch.tableidx
 }
 
-define i32 @unreachable(i32 %x)  {
+define i32 @unreachable_case(i32 %x)  {
 entry:
   switch i32 %x, label %sw.default [
     i32 0, label %sw.bb
     i32 1, label %sw.bb
     i32 2, label %sw.bb
     i32 3, label %sw.bb1
     i32 4, label %sw.bb2
     i32 5, label %sw.bb3
     i32 6, label %sw.bb3
     i32 7, label %sw.bb3
     i32 8, label %sw.bb3
   ]
 
 sw.bb: br label %return
 sw.bb1: unreachable
 sw.bb2: br label %return
 sw.bb3: br label %return
-sw.default: unreachable
+sw.default: br label %return
 
 return:
-  %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ]
+  %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ]
   ret i32 %retval.0
 
-; CHECK-LABEL: @unreachable(
+; CHECK-LABEL: @unreachable_case(
 ; CHECK: switch.lookup:
-; CHECK: getelementptr inbounds [5 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
+; CHECK: getelementptr inbounds [9 x i32]* @switch.table6, i32 0, i32 %switch.tableidx
 }
 
 ; Don't create a table with illegal type
 define i96 @illegaltype(i32 %c) {
 entry:
   switch i32 %c, label %sw.default [
     i32 42, label %return
     i32 43, label %sw.bb1

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

unreachable:
   unreachable
 a:
   %0 = call i32 @f(i32 0)
   ret i32 %0
 b:
   %1 = call i32 @f(i32 1)
   ret i32 %1
 }
+
+
+define i32 @unreachable2(i32 %x) {
+; CHECK-LABEL: @unreachable2
+; CHECK: x.off = add i32 %x, -5
+; CHECK: %switch = icmp ult i32 %x.off, 3
+; CHECK: br i1 %switch, label %a, label %b
+
+entry:
+  ; Note: folding the most popular case destination into the default
+  ; would prevent switch-to-icmp here.
+  switch i32 %x, label %unreachable [
+    i32 5, label %a
+    i32 6, label %a
+    i32 7, label %a
+    i32 10, label %b
+    i32 20, label %b
+  ]
+unreachable:
+  unreachable
+a:
+  %0 = call i32 @f(i32 0)
+  ret i32 %0
+b:
+  %1 = call i32 @f(i32 1)
+  ret i32 %1
+}

llvm/trunk/test/Transforms/SimplifyCFG/switch-to-select-two-case.ll

 
 sw.epilog:
   br label %return
 
 return:
   %retval.0 = phi i32 [ 4, %sw.epilog ], [ 2, %sw.bb1 ], [ 10, %sw.bb ]
   ret i32 %retval.0
 }
-
-; int foo1_without_default(int a) {
-;   switch(a) {
-;     case 10:
-;       return 10;
-;     case 20:
-;       return 2;
-;   }
-;   __builtin_unreachable();
-; }
-
-define i32 @foo1_without_default(i32 %a) {
-; CHECK-LABEL: @foo1_without_default
-; CHECK: %switch.selectcmp = icmp eq i32 %a, 10
-; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 10, i32 2
-; CHECK-NOT: %switch.selectcmp1
-entry:
-  switch i32 %a, label %sw.epilog [
-    i32 10, label %sw.bb
-    i32 20, label %sw.bb1
-  ]
-
-sw.bb:
-  br label %return
-
-sw.bb1:
-  br label %return
-
-sw.epilog:
-  unreachable
-
-return:
-  %retval.0 = phi i32 [ 2, %sw.bb1 ], [ 10, %sw.bb ]
-  ret i32 %retval.0
-}