Index: llvm/include/llvm/Target/TargetLowering.h =================================================================== --- llvm/include/llvm/Target/TargetLowering.h +++ llvm/include/llvm/Target/TargetLowering.h @@ -1008,12 +1008,15 @@ return UseUnderscoreLongJmp; } - /// Return integer threshold on number of blocks to use jump tables rather - /// than if sequence. - int getMinimumJumpTableEntries() const { + /// Return lower limit for number of blocks in a jump table. + unsigned getMinimumJumpTableEntries() const { return MinimumJumpTableEntries; } + /// Return upper limit for number of entries in a jump table. + /// Zero if no limit. + unsigned getMaximumJumpTableSize() const; + /// If a physical register, this specifies the register that /// llvm.savestack/llvm.restorestack should save and restore. unsigned getStackPointerRegisterToSaveRestore() const { @@ -1339,12 +1342,15 @@ UseUnderscoreLongJmp = Val; } - /// Indicate the number of blocks to generate jump tables rather than if - /// sequence. - void setMinimumJumpTableEntries(int Val) { + /// Indicate the minimum number of blocks to generate jump tables. + void setMinimumJumpTableEntries(unsigned Val) { MinimumJumpTableEntries = Val; } + /// Indicate the maximum number of entries in jump tables. + /// Set to zero to generate unlimited jump tables. + void setMaximumJumpTableSize(unsigned); + /// If set to a physical register, this specifies the register that /// llvm.savestack/llvm.restorestack should save and restore. void setStackPointerRegisterToSaveRestore(unsigned R) { Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -8324,26 +8324,38 @@ if (!areJTsAllowed(TLI, SI)) return; - const int64_t N = Clusters.size(); - const unsigned MinJumpTableSize = TLI.getMinimumJumpTableEntries(); + const bool OptForSize = DefaultMBB->getParent()->getFunction()->optForSize(); - // TotalCases[i]: Total nbr of cases in Clusters[0..i]. - SmallVector TotalCases(N); + const unsigned N = Clusters.size(); + const unsigned MinJumpTableEntries = TLI.getMinimumJumpTableEntries(); + const unsigned MaxJumpTableSize = + OptForSize ? UINT_MAX : TLI.getMaximumJumpTableSize() ? + TLI.getMaximumJumpTableSize() : UINT_MAX; + + if (N < 2 || N < MinJumpTableEntries) + return; + // Total number of cases in Clusters[0..N]. + SmallVector TotalCases(N); + // Total number of gaps between Clusters[0..N]. + SmallVector TotalGaps(N); for (unsigned i = 0; i < N; ++i) { - APInt Hi = Clusters[i].High->getValue(); - APInt Lo = Clusters[i].Low->getValue(); - TotalCases[i] = (Hi - Lo).getLimitedValue() + 1; - if (i != 0) + TotalCases[i] = (Clusters[i].High->getValue() - + Clusters[i].Low->getValue()).getLimitedValue() + 1; + if (i != 0) { TotalCases[i] += TotalCases[i - 1]; + TotalGaps[i] = (Clusters[i].Low->getValue() - + Clusters[i - 1].High->getValue()).getLimitedValue() - 1; + TotalGaps[i] += TotalGaps[i - 1]; + } } - unsigned MinDensity = JumpTableDensity; - if (DefaultMBB->getParent()->getFunction()->optForSize()) - MinDensity = OptsizeJumpTableDensity; - if (N >= MinJumpTableSize - && isDense(Clusters, &TotalCases[0], 0, N - 1, MinDensity)) { - // Cheap case: the whole range might be suitable for jump table. + const unsigned MinDensity = + OptForSize ? OptsizeJumpTableDensity : JumpTableDensity; + + // Cheap case: the whole range may be suitable for a jump table. + if (TotalCases[N - 1] + TotalGaps[N - 1] <= MaxJumpTableSize && + isDense(Clusters, &TotalCases[0], 0, N - 1, MinDensity)) { CaseCluster JTCluster; if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) { Clusters[0] = JTCluster; @@ -8363,42 +8375,43 @@ // order. In the choice between two optimal partitionings, it picks the one // which yields more jump tables. - // MinPartitions[i] is the minimum nbr of partitions of Clusters[i..N-1]. + // MinPartitions[i] is the minimum number of partitions of Clusters[i..N - 1]. SmallVector MinPartitions(N); - // LastElement[i] is the last element of the partition starting at i. + // LastElement[i] is the last element of the partition starting at i - 1. SmallVector LastElement(N); - // NumTables[i]: nbr of >= MinJumpTableSize partitions from Clusters[i..N-1]. + // NumTables[i] is the number of partitions from Clusters[i..N - 1]. SmallVector NumTables(N); - // Base case: There is only one way to partition Clusters[N-1]. + // Base case: there is only one way to partition Clusters[N - 1]. MinPartitions[N - 1] = 1; LastElement[N - 1] = N - 1; - assert(MinJumpTableSize > 1); NumTables[N - 1] = 0; - // Note: loop indexes are signed to avoid underflow. - for (int64_t i = N - 2; i >= 0; i--) { - // Find optimal partitioning of Clusters[i..N-1]. - // Baseline: Put Clusters[i] into a partition on its own. - MinPartitions[i] = MinPartitions[i + 1] + 1; - LastElement[i] = i; - NumTables[i] = NumTables[i + 1]; + for (unsigned i = N - 1; i > 0; --i) { + // Find optimal partitioning of Clusters[i - 1..N - 1]. + // Baseline: put Clusters[i - 1] into a partition on its own. + MinPartitions[i - 1] = MinPartitions[i] + 1; + LastElement[i - 1] = i - 1; + NumTables[i - 1] = NumTables[i]; // Search for a solution that results in fewer partitions. - for (int64_t j = N - 1; j > i; j--) { - // Try building a partition from Clusters[i..j]. - if (isDense(Clusters, &TotalCases[0], i, j, MinDensity)) { - unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]); - bool IsTable = j - i + 1 >= MinJumpTableSize; - 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. - if (NumPartitions < MinPartitions[i] || - (NumPartitions == MinPartitions[i] && Tables > NumTables[i])) { - MinPartitions[i] = NumPartitions; - LastElement[i] = j; - NumTables[i] = Tables; + for (unsigned j = N - 1; j > i - 1; --j) {; + // Try building a partition from Clusters[i - 1..j]. + unsigned JumpTableSize = TotalCases[j] - TotalCases[i - 1] + + TotalGaps[j] - TotalGaps[i - 1]; + if (JumpTableSize <= MaxJumpTableSize && + isDense(Clusters, &TotalCases[0], i - 1, j, MinDensity)) { + unsigned NumPartitions = (j == N - 1 ? 0 : MinPartitions[j + 1]) + 1; + unsigned Tables = (j == N - 1 ? 0 : NumTables[j + 1]) + + (MinJumpTableEntries <= j - i); + + // If it leads to fewer partitions or to as many partitions but with + // more jump tables, then it is a better partitioning. + if (NumPartitions < MinPartitions[i - 1] || + (NumPartitions == MinPartitions[i] && Tables > NumTables[i - 1])) { + MinPartitions[i - 1] = NumPartitions; + LastElement[i - 1] = j; + NumTables[i - 1] = Tables; } } } @@ -8413,7 +8426,7 @@ unsigned NumClusters = Last - First + 1; CaseCluster JTCluster; - if (NumClusters >= MinJumpTableSize && + if (NumClusters >= MinJumpTableEntries && buildJumpTable(Clusters, First, Last, SI, DefaultMBB, JTCluster)) { Clusters[DstIndex++] = JTCluster; } else { Index: llvm/lib/CodeGen/TargetLoweringBase.cpp =================================================================== --- llvm/lib/CodeGen/TargetLoweringBase.cpp +++ llvm/lib/CodeGen/TargetLoweringBase.cpp @@ -44,6 +44,10 @@ cl::desc("Do not create extra branches to split comparison logic."), cl::Hidden); +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.")); + // 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 // is best represented as control flow. Therefore, the default value N should be @@ -1839,3 +1843,11 @@ Value *TargetLoweringBase::getSSPStackGuardCheck(const Module &M) const { return nullptr; } + +unsigned TargetLoweringBase::getMaximumJumpTableSize() const { + return MaximumJumpTableSize; +} + +void TargetLoweringBase::setMaximumJumpTableSize(unsigned Val) { + MaximumJumpTableSize = Val; +} Index: llvm/lib/Target/AArch64/AArch64ISelLowering.cpp =================================================================== --- llvm/lib/Target/AArch64/AArch64ISelLowering.cpp +++ llvm/lib/Target/AArch64/AArch64ISelLowering.cpp @@ -523,6 +523,12 @@ setPrefFunctionAlignment(STI.getPrefFunctionAlignment()); setPrefLoopAlignment(STI.getPrefLoopAlignment()); + // Only change the limit for entries in a jump table if specified by + // the subtarget, but not at the command line. + unsigned MaxJT = STI.getMaximumJumpTableSize(); + if (MaxJT && getMaximumJumpTableSize() == 0) + setMaximumJumpTableSize(MaxJT); + setHasExtractBitsInsn(true); setOperationAction(ISD::INTRINSIC_WO_CHAIN, MVT::Other, Custom); Index: llvm/lib/Target/AArch64/AArch64Subtarget.h =================================================================== --- llvm/lib/Target/AArch64/AArch64Subtarget.h +++ llvm/lib/Target/AArch64/AArch64Subtarget.h @@ -91,6 +91,7 @@ unsigned MaxPrefetchIterationsAhead = UINT_MAX; unsigned PrefFunctionAlignment = 0; unsigned PrefLoopAlignment = 0; + unsigned MaxJumpTableSize = 0; // ReserveX18 - X18 is not available as a general purpose register. bool ReserveX18; @@ -203,6 +204,8 @@ unsigned getPrefFunctionAlignment() const { return PrefFunctionAlignment; } unsigned getPrefLoopAlignment() const { return PrefLoopAlignment; } + unsigned getMaximumJumpTableSize() const { return MaxJumpTableSize; } + /// CPU has TBI (top byte of addresses is ignored during HW address /// translation) and OS enables it. bool supportsAddressTopByteIgnored() const; Index: llvm/lib/Target/AArch64/AArch64Subtarget.cpp =================================================================== --- llvm/lib/Target/AArch64/AArch64Subtarget.cpp +++ llvm/lib/Target/AArch64/AArch64Subtarget.cpp @@ -65,6 +65,7 @@ case ExynosM1: PrefFunctionAlignment = 4; PrefLoopAlignment = 3; + MaxJumpTableSize = 14; break; case Kryo: MaxInterleaveFactor = 4; Index: llvm/test/CodeGen/Generic/max-jump-table.ll =================================================================== --- /dev/null +++ llvm/test/CodeGen/Generic/max-jump-table.ll @@ -0,0 +1,86 @@ +; RUN: llc %s -O2 -print-machineinstrs -jump-table-density=40 -o - 2>%t; FileCheck %s --check-prefix=CHECK --check-prefix=CHECK0 <%t +; RUN: llc %s -O2 -print-machineinstrs -jump-table-density=40 -max-jump-table=4 -o - 2>%t; FileCheck %s --check-prefix=CHECK --check-prefix=CHECK4 <%t +; RUN: llc %s -O2 -print-machineinstrs -jump-table-density=40 -max-jump-table=8 -o - 2>%t; FileCheck %s --check-prefix=CHECK --check-prefix=CHECK8 <%t + +declare void @ext(i32) + +define i32 @jt1(i32 %a, i32 %b) { +entry: + switch i32 %a, label %return [ + i32 1, label %bb + i32 2, label %bb1 + i32 3, label %bb3 + i32 4, label %bb5 + i32 5, label %bb7 + i32 6, label %bb9 + i32 7, label %bb11 + i32 8, label %bb13 + i32 9, label %bb15 + i32 10, label %bb17 + i32 11, label %bb19 + i32 12, label %bb21 + i32 13, label %bb23 + i32 14, label %bb25 + i32 15, label %bb27 + i32 16, label %bb29 + i32 17, label %bb31 + ] +; CHECK-LABEL: function jt1: +; CHECK-NEXT: Jump Tables: +; CHECK0-NEXT: jt#0: +; CHECK0-NOT: jt#1: +; CHECK4-NEXT: jt#0: +; CHECK4-SAME: jt#1: +; CHECK4-SAME: jt#2: +; CHECK4-SAME: jt#3: +; CHECK4-NOT: jt#4: +; CHECK8-NEXT: jt#0: +; CHECK8-SAME: jt#1: +; CHECK8-NOT: jt#2: + +bb: tail call void @ext(i32 %b) br label %return +bb1: tail call void @ext(i32 %b) br label %return +bb3: tail call void @ext(i32 %b) br label %return +bb5: tail call void @ext(i32 %b) br label %return +bb7: tail call void @ext(i32 %b) br label %return +bb9: tail call void @ext(i32 %b) br label %return +bb11: tail call void @ext(i32 %b) br label %return +bb13: tail call void @ext(i32 %b) br label %return +bb15: tail call void @ext(i32 %b) br label %return +bb17: tail call void @ext(i32 %b) br label %return +bb19: tail call void @ext(i32 %b) br label %return +bb21: tail call void @ext(i32 %b) br label %return +bb23: tail call void @ext(i32 %b) br label %return +bb25: tail call void @ext(i32 %b) br label %return +bb27: tail call void @ext(i32 %b) br label %return +bb29: tail call void @ext(i32 %b) br label %return +bb31: tail call void @ext(i32 %b) br label %return + +return: ret i32 %b +} + +define void @jt2(i32 %x) { +entry: + switch i32 %x, label %return [ + i32 1, label %bb1 + i32 2, label %bb2 + i32 3, label %bb3 + i32 4, label %bb4 + + i32 14, label %bb5 + i32 15, label %bb6 + ] +; CHECK-LABEL: function jt2: +; 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{{$}} + +bb1: tail call void @ext(i32 1) br label %return +bb2: tail call void @ext(i32 2) br label %return +bb3: tail call void @ext(i32 3) br label %return +bb4: tail call void @ext(i32 4) br label %return +bb5: tail call void @ext(i32 5) br label %return +bb6: tail call void @ext(i32 6) br label %return +return: ret void +}