Index: llvm/include/llvm/Target/TargetLowering.h
===================================================================
--- llvm/include/llvm/Target/TargetLowering.h
+++ llvm/include/llvm/Target/TargetLowering.h
@@ -1027,9 +1027,7 @@
}
/// Return lower limit for number of blocks in a jump table.
- unsigned getMinimumJumpTableEntries() const {
- return MinimumJumpTableEntries;
- }
+ unsigned getMinimumJumpTableEntries() const;
/// Return upper limit for number of entries in a jump table.
/// Zero if no limit.
@@ -1361,9 +1359,7 @@
}
/// Indicate the minimum number of blocks to generate jump tables.
- void setMinimumJumpTableEntries(unsigned Val) {
- MinimumJumpTableEntries = Val;
- }
+ void setMinimumJumpTableEntries(unsigned Val);
/// Indicate the maximum number of entries in jump tables.
/// Set to zero to generate unlimited jump tables.
@@ -1930,9 +1926,6 @@
/// Defaults to false.
bool UseUnderscoreLongJmp;
- /// Number of blocks threshold to use jump tables.
- int MinimumJumpTableEntries;
-
/// Information about the contents of the high-bits in boolean values held in
/// a type wider than i1. See getBooleanContents.
BooleanContent BooleanContents;
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -8429,9 +8429,10 @@
const int64_t N = Clusters.size();
const unsigned MinJumpTableEntries = TLI.getMinimumJumpTableEntries();
+ const unsigned SmallJumpTableEntries = MinJumpTableEntries / 2;
const unsigned MaxJumpTableSize =
- OptForSize ? UINT_MAX : TLI.getMaximumJumpTableSize() ?
- TLI.getMaximumJumpTableSize() : UINT_MAX;
+ OptForSize || TLI.getMaximumJumpTableSize() == 0
+ ? UINT_MAX : TLI.getMaximumJumpTableSize();
if (N < 2 || N < MinJumpTableEntries)
return;
@@ -8455,7 +8456,6 @@
.getLimitedValue(UINT_MAX - 1) + 1;
if (JumpTableSize <= MaxJumpTableSize &&
isDense(Clusters, TotalCases, 0, N - 1, MinDensity)) {
-
CaseCluster JTCluster;
if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) {
Clusters[0] = JTCluster;
@@ -8479,13 +8479,15 @@
SmallVector<unsigned, 8> MinPartitions(N);
// LastElement[i] is the last element of the partition starting at i.
SmallVector<unsigned, 8> LastElement(N);
- // NumTables[i]: nbr of >= MinJumpTableSize partitions from Clusters[i..N-1].
- SmallVector<unsigned, 8> NumTables(N);
+ // PartitionScore[i]: Partitions are scored if resulting in a jump table or
+ // by adding a small number of links in the if-then-else chain, especially if
+ // only one link is added
+ SmallVector<unsigned, 8> PartitionScore(N);
// Base case: There is only one way to partition Clusters[N-1].
MinPartitions[N - 1] = 1;
LastElement[N - 1] = N - 1;
- NumTables[N - 1] = 0;
+ PartitionScore[N - 1] = 0;
// Note: loop indexes are signed to avoid underflow.
for (int64_t i = N - 2; i >= 0; i--) {
@@ -8493,10 +8495,10 @@
// Baseline: Put Clusters[i] into a partition on its own.
MinPartitions[i] = MinPartitions[i + 1] + 1;
LastElement[i] = i;
- NumTables[i] = NumTables[i + 1];
+ PartitionScore[i] = PartitionScore[i + 1];
// Search for a solution that results in fewer partitions.
- for (int64_t j = N - 1; j > i; j--) {
+ for (int64_t j = N - 1; j >= i; j--) {
// Try building a partition from Clusters[i..j].
JumpTableSize = (Clusters[j].High->getValue() -
Clusters[i].Low->getValue())
@@ -8504,16 +8506,19 @@
if (JumpTableSize <= MaxJumpTableSize &&
isDense(Clusters, TotalCases, i, j, MinDensity)) {
unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]);
- bool IsTable = j - i + 1 >= MinJumpTableEntries;
- unsigned Tables = IsTable + (j == N - 1 ? 0 : NumTables[j + 1]);
-
- // If this j leads to fewer partitions, or same number of partitions
- // with more lookup tables, it is a better partitioning.
+ int64_t NumEntries = j - i + 1;
+ bool IsTable = NumEntries >= MinJumpTableEntries;
+ bool IsSmall = NumEntries <= SmallJumpTableEntries;
+ bool IsOnlyOne = NumEntries == 1;
+ unsigned Score = IsTable + IsSmall + IsOnlyOne;
+
+ // If this leads to fewer partitions, or to the same number of
+ // partitions with better score, it is a better partitioning.
if (NumPartitions < MinPartitions[i] ||
- (NumPartitions == MinPartitions[i] && Tables > NumTables[i])) {
+ (NumPartitions == MinPartitions[i] && Score > PartitionScore[i])) {
MinPartitions[i] = NumPartitions;
LastElement[i] = j;
- NumTables[i] = Tables;
+ PartitionScore[i] = Score;
}
}
}
Index: llvm/lib/CodeGen/TargetLoweringBase.cpp
===================================================================
--- llvm/lib/CodeGen/TargetLoweringBase.cpp
+++ llvm/lib/CodeGen/TargetLoweringBase.cpp
@@ -44,9 +44,13 @@
cl::desc("Do not create extra branches to split comparison logic."),
cl::Hidden);
+static cl::opt<unsigned> MinimumJumpTableEntries
+ ("min-jump-table-entries", cl::init(4), cl::Hidden,
+ cl::desc("Set minimum number of entries to use a jump table."));
+
static cl::opt<unsigned> MaximumJumpTableSize
- ("max-jump-table", cl::init(0), cl::Hidden,
- cl::desc("Set maximum number of jump table entries; zero for no limit."));
+ ("max-jump-table-size", cl::init(0), cl::Hidden,
+ cl::desc("Set maximum size of jump table; zero for no limit."));
// Although this default value is arbitrary, it is not random. It is assumed
// that a condition that evaluates the same way by a higher percentage than this
@@ -825,7 +829,6 @@
PrefLoopAlignment = 0;
GatherAllAliasesMaxDepth = 6;
MinStackArgumentAlignment = 1;
- MinimumJumpTableEntries = 4;
// TODO: the default will be switched to 0 in the next commit, along
// with the Target-specific changes necessary.
MaxAtomicSizeInBitsSupported = 1024;
@@ -1852,6 +1855,14 @@
return nullptr;
}
+unsigned TargetLoweringBase::getMinimumJumpTableEntries() const {
+ return MinimumJumpTableEntries;
+}
+
+void TargetLoweringBase::setMinimumJumpTableEntries(unsigned Val) {
+ MinimumJumpTableEntries = Val;
+}
+
unsigned TargetLoweringBase::getMaximumJumpTableSize() const {
return MaximumJumpTableSize;
}
Index: llvm/test/CodeGen/AArch64/max-jump-table.ll
===================================================================
--- llvm/test/CodeGen/AArch64/max-jump-table.ll
+++ llvm/test/CodeGen/AArch64/max-jump-table.ll
@@ -1,7 +1,7 @@
-; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK0 <%t
-; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -max-jump-table=4 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK4 <%t
-; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -max-jump-table=8 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECK8 <%t
-; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -mcpu=exynos-m1 -o - 2>%t; FileCheck %s --check-prefixes=CHECK,CHECKM1 <%t
+; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -o /dev/null 2> %t; FileCheck %s --check-prefixes=CHECK,CHECK0 < %t
+; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -max-jump-table-size=4 -o /dev/null 2> %t; FileCheck %s --check-prefixes=CHECK,CHECK4 < %t
+; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -max-jump-table-size=8 -o /dev/null 2> %t; FileCheck %s --check-prefixes=CHECK,CHECK8 < %t
+; RUN: llc %s -O2 -print-machineinstrs -mtriple=aarch64-linux-gnu -jump-table-density=40 -mcpu=exynos-m1 -o /dev/null 2> %t; FileCheck %s --check-prefixes=CHECK,CHECKM1 < %t
declare void @ext(i32)
@@ -27,7 +27,7 @@
i32 17, label %bb17
]
; CHECK-LABEL: function jt1:
-; CHECK: Jump Tables:
+; CHECK-NEXT: Jump Tables:
; CHECK0-NEXT: jt#0:
; CHECK0-NOT: jt#1:
; CHECK4-NEXT: jt#0:
@@ -37,10 +37,9 @@
; CHECK4-NOT: jt#4:
; CHECK8-NEXT: jt#0:
; CHECK8-SAME: jt#1:
-; CHECK8-SAME: jt#2: BB#14 BB#15 BB#16 BB#17{{$}}
-; CHECK8-NOT: jt#3:
+; CHECK8-NOT: jt#2:
; CHECKM1-NEXT: jt#0:
-; CHECKM1-SAME: jt#1: BB#13 BB#14 BB#15 BB#16 BB#17{{$}}
+; CHECKM1-SAME: jt#1
; CHECKM1-NOT: jt#2:
; CHEC-NEXT: Function Live Ins:
@@ -77,7 +76,7 @@
i32 15, label %bb6
]
; CHECK-LABEL: function jt2:
-; CHECK: Jump Tables:
+; CHECK-NEXT: Jump Tables:
; CHECK0-NEXT: jt#0: BB#1 BB#2 BB#3 BB#4 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#7 BB#5 BB#6{{$}}
; CHECK4-NEXT: jt#0: BB#1 BB#2 BB#3 BB#4{{$}}
; CHECK8-NEXT: jt#0: BB#1 BB#2 BB#3 BB#4{{$}}