Prevent binary-tree deterioration in sparse switch statements.
This addresses part of llvm.org/PR22262. Specifically, it prevents
considering the densities of sub-ranges that have fewer than
TLI.getMinimumJumpTableEntries() elements. Those densities won't help
jump tables.
This is not a complete solution but works around the most pressing
issue.
Review: http://reviews.llvm.org/D7070
llvm-svn: 226600
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 2ee276f..ea76bc6 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2420,6 +2420,7 @@
DEBUG(dbgs() << "Selecting best pivot: \n"
<< "First: " << First << ", Last: " << Last <<'\n'
<< "LSize: " << LSize << ", RSize: " << RSize << '\n');
+ const TargetLowering &TLI = DAG.getTargetLoweringInfo();
for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
J!=E; ++I, ++J) {
const APInt &LEnd = cast<ConstantInt>(I->High)->getValue();
@@ -2429,10 +2430,16 @@
"Invalid case distance");
// Use volatile double here to avoid excess precision issues on some hosts,
// e.g. that use 80-bit X87 registers.
+ // Only consider the density of sub-ranges that actually have sufficient
+ // entries to be lowered as a jump table.
volatile double LDensity =
- LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
+ LSize.ult(TLI.getMinimumJumpTableEntries())
+ ? 0.0
+ : LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
volatile double RDensity =
- RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
+ RSize.ult(TLI.getMinimumJumpTableEntries())
+ ? 0.0
+ : RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
volatile double Metric = Range.logBase2() * (LDensity + RDensity);
// Should always split in some non-trivial place
DEBUG(dbgs() <<"=>Step\n"
@@ -2450,13 +2457,8 @@
RSize -= J->size();
}
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- if (areJTsAllowed(TLI)) {
- // If our case is dense we *really* should handle it earlier!
- assert((FMetric > 0) && "Should handle dense range earlier!");
- } else {
+ if (FMetric == 0 || !areJTsAllowed(TLI))
Pivot = CR.Range.first + Size/2;
- }
splitSwitchCase(CR, Pivot, WorkList, SV, SwitchBB);
return true;
}
diff --git a/llvm/test/CodeGen/X86/switch-bt.ll b/llvm/test/CodeGen/X86/switch-bt.ll
index a80002b..065d8cd 100644
--- a/llvm/test/CodeGen/X86/switch-bt.ll
+++ b/llvm/test/CodeGen/X86/switch-bt.ll
@@ -99,3 +99,61 @@
if.end:
ret void
}
+
+; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
+; created binary tree search. See PR22262.
+define void @test4(i32 %x, i32* %y) {
+; CHECK-LABEL: test4:
+
+entry:
+ switch i32 %x, label %sw.default [
+ i32 10, label %sw.bb
+ i32 20, label %sw.bb1
+ i32 30, label %sw.bb2
+ i32 40, label %sw.bb3
+ i32 50, label %sw.bb4
+ i32 60, label %sw.bb5
+ ]
+sw.bb:
+ store i32 1, i32* %y
+ br label %sw.epilog
+sw.bb1:
+ store i32 2, i32* %y
+ br label %sw.epilog
+sw.bb2:
+ store i32 3, i32* %y
+ br label %sw.epilog
+sw.bb3:
+ store i32 4, i32* %y
+ br label %sw.epilog
+sw.bb4:
+ store i32 5, i32* %y
+ br label %sw.epilog
+sw.bb5:
+ store i32 6, i32* %y
+ br label %sw.epilog
+sw.default:
+ store i32 7, i32* %y
+ br label %sw.epilog
+sw.epilog:
+ ret void
+
+; The balanced binary switch here would start with a comparison against 39, but
+; it is currently starting with 29 because of the density-sum heuristic.
+; CHECK: cmpl $29
+; CHECK: jg
+; CHECK: cmpl $10
+; CHECK: jne
+; CHECK: cmpl $49
+; CHECK: jg
+; CHECK: cmpl $30
+; CHECK: jne
+; CHECK: cmpl $20
+; CHECK: jne
+; CHECK: cmpl $50
+; CHECK: jne
+; CHECK: cmpl $40
+; CHECK: jne
+; CHECK: cmpl $60
+; CHECK: jne
+}