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 SmallNumberOfEntries = 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,23 @@ SmallVector MinPartitions(N); // LastElement[i] is the last element of the partition starting at i. SmallVector LastElement(N); - // NumTables[i]: nbr of >= MinJumpTableSize partitions from Clusters[i..N-1]. - SmallVector NumTables(N); + // PartitionScore[i] is used to break ties when choosing between two + // partitionings resulting in the same number of partitions. + SmallVector PartitionScore(N); + // Weights relative to generating a jump table to score partitions. + // Here, a small number of comparisons is considered as good as a jump table + // and a single comparison is considered better than a jump table. + enum PartitionScoreEnum : unsigned { + None = 0, + Table = 1, + Small = 1, + One = 2 + }; // 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] = PartitionScoreEnum::Table; // Note: loop indexes are signed to avoid underflow. for (int64_t i = N - 2; i >= 0; i--) { @@ -8493,10 +8503,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] + 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 +8514,26 @@ 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]); + int64_t NumEntries = j - i + 1; + + bool IsTable = NumEntries >= MinJumpTableEntries; + bool IsSmall = NumEntries <= SmallNumberOfEntries; + bool IsOne = NumEntries == 1; + + unsigned Score = j == N - 1 + ? PartitionScoreEnum::None : PartitionScore[j + 1]; + if (IsTable) + Score += PartitionScoreEnum::Table; + else if (IsSmall || IsOne) + Score += IsOne ? PartitionScoreEnum::One : PartitionScoreEnum::Small; - // If this j leads to fewer partitions, or same number of partitions - // with more lookup tables, it is a better partitioning. + // 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 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 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{{$}}