From 7294b58ecdb430d1473d0a9220a234e62a710d54 Mon Sep 17 00:00:00 2001
From: Anton Korobeynikov <asl@math.spbu.ru>
Date: Wed, 9 May 2007 20:07:08 +0000
Subject: [PATCH 1/1] Do not assert, when case range split metric is zero and
 JTs are not allowed: just emit binary tree in this case. This fixes PR1403.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36959 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 17 +++++++----
 test/CodeGen/SPARC/2007-05-09-JumpTables.ll   | 30 +++++++++++++++++++
 2 files changed, 42 insertions(+), 5 deletions(-)
 create mode 100644 test/CodeGen/SPARC/2007-05-09-JumpTables.ll

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index b70366357d9..075a9c4a464 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -1462,6 +1462,11 @@ bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
   return true;
 }
 
+static inline bool areJTsAllowed(const TargetLowering &TLI) {
+  return (TLI.isOperationLegal(ISD::BR_JT, MVT::Other) ||
+          TLI.isOperationLegal(ISD::BRIND, MVT::Other));
+}
+  
 /// handleJTSwitchCase - Emit jumptable for current switch case range
 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
                                               CaseRecVector& WorkList,
@@ -1478,9 +1483,7 @@ bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
        I!=E; ++I)
     TSize += I->size();
 
-  if ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
-       !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
-      TSize <= 3)
+  if (!areJTsAllowed(TLI) || TSize <= 3)
     return false;
   
   double Density = (double)TSize / (double)((Last - First) + 1ULL);  
@@ -1622,8 +1625,12 @@ bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
     LSize += J->size();
     RSize -= J->size();
   }
-  // If our case is dense we *really* should handle it earlier!
-  assert((FMetric > 0) && "Should handle dense range earlier!");
+  if (areJTsAllowed(TLI)) {
+    // If our case is dense we *really* should handle it earlier!
+    assert((FMetric > 0) && "Should handle dense range earlier!");
+  } else {
+    Pivot = CR.Range.first + Size/2;
+  }
   
   CaseRange LHSR(CR.Range.first, Pivot);
   CaseRange RHSR(Pivot, CR.Range.second);
diff --git a/test/CodeGen/SPARC/2007-05-09-JumpTables.ll b/test/CodeGen/SPARC/2007-05-09-JumpTables.ll
new file mode 100644
index 00000000000..a014acefa90
--- /dev/null
+++ b/test/CodeGen/SPARC/2007-05-09-JumpTables.ll
@@ -0,0 +1,30 @@
+; RUN: llvm-as < %s | llc -march=sparc
+
+; We cannot emit jump tables on Sparc, but we should correctly handle this case.
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
+
+define i32 @foo(i32 %f) {
+entry:
+	switch i32 %f, label %bb14 [
+		 i32 0, label %UnifiedReturnBlock
+		 i32 1, label %bb4
+		 i32 2, label %bb7
+		 i32 3, label %bb10
+	]
+
+bb4:		; preds = %entry
+	ret i32 2
+
+bb7:		; preds = %entry
+	ret i32 5
+
+bb10:		; preds = %entry
+	ret i32 9
+
+bb14:		; preds = %entry
+	ret i32 0
+
+UnifiedReturnBlock:		; preds = %entry
+	ret i32 1
+}
-- 
2.34.1