SelectionDAG switch lowering: Replace unreachable default with most popular case.

[hans]

Summary

This can significantly reduce the size of the switch, allowing for more
efficient lowering.

SimplifyCFG currently does this transformation, but I'm working on
changing that to make it possible to exploit unreachable default cases.

I also worked with the idea of exploiting unreachable defaults by
omitting the range check for jump tables, but always ended up with a
non-neglible binary size increase. It might be worth looking into some more.

(This was broken out of http://reviews.llvm.org/D6471)

[majnemer]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2711 ↗

(On Diff #16875)

DenseMap<const BasicBlock *, uint64_t>

2728–2735 ↗

(On Diff #16875)

How about remove_if(Cases.begin(), Cases.end(), ...

[hans]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2711 ↗

(On Diff #16875)

Done.

2728–2735 ↗

(On Diff #16875)

Nice :) Done.

[hans]

Addressing David's comments.

[majnemer]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2732 ↗

(On Diff #17008)

const Case &C

[majnemer]

LGTM with tweaks.

[hans]

Closed by commit rL223566 (authored by @hans).

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) {
   MachineBasicBlock *SwitchMBB = FuncInfo.MBB;
 
   // Figure out which block is immediately after the current one.
   MachineBasicBlock *NextBlock = nullptr;
   if (SwitchMBB + 1 != FuncInfo.MF->end())
     NextBlock = SwitchMBB + 1;
 
+
+  // Create a vector of Cases, sorted so that we can efficiently create a binary
+  // search tree from them.
+  CaseVector Cases;
+  Clusterify(Cases, SI);
+
+  // Get the default destination MBB.
   MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
 
-  // If there is only the default destination, branch to it if it is not the
-  // next basic block.  Otherwise, just fall through.
-  if (!SI.getNumCases()) {
+  if (isa<UnreachableInst>(SI.getDefaultDest()->getFirstNonPHIOrDbg()) &&
+      !Cases.empty()) {
+    // Replace an unreachable default destination with the most popular case
+    // destination.
+    DenseMap<const BasicBlock *, uint64_t> Popularity;
+    uint64_t MaxPop = 0;
+    const BasicBlock *MaxBB = nullptr;
+    for (auto I : SI.cases()) {
+      const BasicBlock *BB = I.getCaseSuccessor();
+      if (++Popularity[BB] > MaxPop) {
+        MaxPop = Popularity[BB];
+        MaxBB = BB;
+      }
+    }
+
+    // Set new default.
+    assert(MaxPop > 0);
+    assert(MaxBB);
+    Default = FuncInfo.MBBMap[MaxBB];
+
+    // Remove cases that were pointing to the destination that is now the default.
+    Cases.erase(std::remove_if(Cases.begin(), Cases.end(),
+                               [&](const Case &C) { return C.BB == Default; }),
+                Cases.end());
+  }
+
+  // If there is only the default destination, go there directly.
+  if (Cases.empty()) {
     // Update machine-CFG edges.
     SwitchMBB->addSuccessor(Default);
 
     // If this is not a fall-through branch, emit the branch.
-    if (Default != NextBlock)
-      DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
-                              MVT::Other, getControlRoot(),
-                              DAG.getBasicBlock(Default)));
-
+    if (Default != NextBlock) {
+      DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
+                              getControlRoot(), DAG.getBasicBlock(Default)));
+    }
     return;
   }
 
-  // If there are any non-default case statements, create a vector of Cases
-  // representing each one, and sort the vector so that we can efficiently
-  // create a binary search tree from them.
-  CaseVector Cases;
-  Clusterify(Cases, SI);
-
-  // Get the Value to be switched on and default basic blocks, which will be
-  // inserted into CaseBlock records, representing basic blocks in the binary
-  // search tree.
+  // Get the Value to be switched on.
   const Value *SV = SI.getCondition();
 
   // Push the initial CaseRec onto the worklist
   CaseRecVector WorkList;
   WorkList.push_back(CaseRec(SwitchMBB,nullptr,nullptr,
                              CaseRange(Cases.begin(),Cases.end())));
 
   while (!WorkList.empty()) {

llvm/trunk/test/CodeGen/X86/2013-10-14-FastISel-incorrect-vreg.ll

 entry:
   %loaded_ptr = load i64 (i64, i64, i64)** %arg, align 8
   %raw = bitcast i64 (i64, i64, i64)* %loaded_ptr to i8*
   switch i1 %bool, label %default [
     i1 true, label %label_true
     i1 false, label %label_end
   ]
 default:
-  unreachable
+  br label %label_end
 
 label_true:
   br label %label_end
 
 label_end:
   %fct_ptr = bitcast i8* %raw to i64 (i64, i64, i64)*
   %res = call i64 %fct_ptr(i64 %arg2, i64 %arg2, i64 %arg2)
   ret i64 %res

 entry:
   %loaded_ptr = load i64 (i64, i64, i64)** %arg, align 8
   %raw = ptrtoint i64 (i64, i64, i64)* %loaded_ptr to i64
   switch i1 %bool, label %default [
     i1 true, label %label_true
     i1 false, label %label_end
   ]
 default:
-  unreachable
+  br label %label_end
 
 label_true:
   br label %label_end
 
 label_end:
   %fct_ptr = inttoptr i64 %raw to i64 (i64, i64, i64)*
   %res = call i64 %fct_ptr(i64 %arg2, i64 %arg2, i64 %arg2)
   ret i64 %res

 entry:
   %loaded_ptr = load i64 (i64, i64, i64)** %arg, align 8
   %raw = bitcast i64 (i64, i64, i64)* %loaded_ptr to i8*
   switch i1 %bool, label %default [
     i1 true, label %label_true
     i1 false, label %label_end
   ]
 default:
-  unreachable
+  br label %label_end
 
 label_true:
   br label %label_end
 
 label_end:
   %fct_int = ptrtoint i8* %raw to i64
   %fct_ptr = inttoptr i64 %fct_int to i64 (i64, i64, i64)*
   %res = call i64 %fct_ptr(i64 %arg2, i64 %arg2, i64 %arg2)
   ret i64 %res
 }

llvm/trunk/test/CodeGen/X86/asm-label.ll

 
 if.then9:                                         ; preds = %if.then
   br label %cleanup
 
 if.end:                                           ; preds = %if.then
   br label %cleanup
 
 cleanup:                                          ; preds = %if.end, %if.then9
-  switch i32 undef, label %unreachable [
+  switch i32 undef, label %default [
     i32 0, label %cleanup.cont
     i32 1, label %if.end11
   ]
 
 cleanup.cont:                                     ; preds = %cleanup
   br label %if.end11
 
 if.end11:                                         ; preds = %cleanup.cont, %cleanup, %land.lhs.true, %entry
   ret void
 
-unreachable:                                      ; preds = %cleanup
-  unreachable
+default:                                          ; preds = %cleanup
+  br label %if.end11
 }

llvm/trunk/test/CodeGen/X86/switch-jump-table.ll

+; RUN: llc -march=x86 < %s | FileCheck %s
+
+
+; An unreachable default destination is replaced with the most popular case label.
+
+define void @sum2(i32 %x, i32* %to) {
+; CHECK-LABEL: sum2:
+; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]]
+; cmpl $3, [[REG]]
+; CHECK: jbe .LBB0_1
+; CHECK: movl $4
+; CHECK: retl
+; CHECK-LABEL: .LBB0_1:
+; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4)
+
+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* %to
+  br label %exit
+bb1:
+  store i32 1, i32* %to
+  br label %exit
+bb2:
+  store i32 2, i32* %to
+  br label %exit
+bb3:
+  store i32 3, i32* %to
+  br label %exit
+bb4:
+  store i32 4, i32* %to
+  br label %exit
+exit:
+  ret void
+default:
+  unreachable
+
+; The jump table has four entries.
+; CHECK-LABEL: .LJTI0_0:
+; CHECK-NEXT: .long  .LBB0_2
+; CHECK-NEXT: .long  .LBB0_3
+; CHECK-NEXT: .long  .LBB0_4
+; CHECK-NEXT: .long  .LBB0_5
+; CHECK-NOT: .long
+}