From ecb26a7f3f93dbef2c749b70e708d19f691c12aa Mon Sep 17 00:00:00 2001 From: Evandro Menezes Date: Thu, 20 Jun 2019 16:34:00 +0000 Subject: [PATCH] [CodeGen] Fix formatting and comments (NFC) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@363947 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/SwitchLoweringUtils.h | 4 +- include/llvm/CodeGen/TargetLowering.h | 1 + lib/CodeGen/SwitchLoweringUtils.cpp | 14 +- test/CodeGen/AArch64/max-jump-table.ll | 168 ++++++++++----------- test/CodeGen/AArch64/min-jump-table.ll | 1 - 5 files changed, 95 insertions(+), 93 deletions(-) diff --git a/include/llvm/CodeGen/SwitchLoweringUtils.h b/include/llvm/CodeGen/SwitchLoweringUtils.h index 5d4dc0d3bcf..75191564bb3 100644 --- a/include/llvm/CodeGen/SwitchLoweringUtils.h +++ b/include/llvm/CodeGen/SwitchLoweringUtils.h @@ -199,11 +199,11 @@ struct BitTestBlock { Cases(std::move(C)), Prob(Pr) {} }; -/// Return the range of value in [First..Last]. +/// Return the range of value within a range. uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First, unsigned Last); -/// Return the number of cases in [First..Last]. +/// Return the number of cases within a range. uint64_t getJumpTableNumCases(const SmallVectorImpl &TotalCases, unsigned First, unsigned Last); diff --git a/include/llvm/CodeGen/TargetLowering.h b/include/llvm/CodeGen/TargetLowering.h index 094d4888380..b22d2a0aa71 100644 --- a/include/llvm/CodeGen/TargetLowering.h +++ b/include/llvm/CodeGen/TargetLowering.h @@ -983,6 +983,7 @@ public: const unsigned MinDensity = getMinimumJumpTableDensity(OptForSize); const unsigned MaxJumpTableSize = OptForSize ? UINT_MAX : getMaximumJumpTableSize(); + // Check whether a range of clusters is dense enough for a jump table. if (Range <= MaxJumpTableSize && (NumCases * 100 >= Range * MinDensity)) { diff --git a/lib/CodeGen/SwitchLoweringUtils.cpp b/lib/CodeGen/SwitchLoweringUtils.cpp index 1909ce116dd..53b6940e06b 100644 --- a/lib/CodeGen/SwitchLoweringUtils.cpp +++ b/lib/CodeGen/SwitchLoweringUtils.cpp @@ -27,7 +27,6 @@ uint64_t SwitchCG::getJumpTableRange(const CaseClusterVector &Clusters, // FIXME: A range of consecutive cases has 100% density, but only requires one // comparison to lower. We should discriminate against such consecutive ranges // in jump tables. - return (HighCase - LowCase).getLimitedValue((UINT64_MAX - 1) / 100) + 1; } @@ -56,14 +55,15 @@ void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters, if (!TLI->areJTsAllowed(SI->getParent()->getParent())) return; - const int64_t N = Clusters.size(); const unsigned MinJumpTableEntries = TLI->getMinimumJumpTableEntries(); const unsigned SmallNumberOfEntries = MinJumpTableEntries / 2; + // Bail if not enough cases. + const int64_t N = Clusters.size(); if (N < 2 || N < MinJumpTableEntries) return; - // TotalCases[i]: Total nbr of cases in Clusters[0..i]. + // Accumulated number of cases in each cluster and those prior to it. SmallVector TotalCases(N); for (unsigned i = 0; i < N; ++i) { const APInt &Hi = Clusters[i].High->getValue(); @@ -73,11 +73,12 @@ void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters, TotalCases[i] += TotalCases[i - 1]; } - // Cheap case: the whole range may be suitable for jump table. uint64_t Range = getJumpTableRange(Clusters,0, N - 1); uint64_t NumCases = getJumpTableNumCases(TotalCases, 0, N - 1); assert(NumCases < UINT64_MAX / 100); assert(Range >= NumCases); + + // Cheap case: the whole range may be suitable for jump table. if (TLI->isSuitableForJumpTable(SI, NumCases, Range)) { CaseCluster JTCluster; if (buildJumpTable(Clusters, 0, N - 1, SI, DefaultMBB, JTCluster)) { @@ -131,10 +132,11 @@ void SwitchCG::SwitchLowering::findJumpTables(CaseClusterVector &Clusters, // 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]. - uint64_t Range = getJumpTableRange(Clusters, i, j); - uint64_t NumCases = getJumpTableNumCases(TotalCases, i, j); + Range = getJumpTableRange(Clusters, i, j); + NumCases = getJumpTableNumCases(TotalCases, i, j); assert(NumCases < UINT64_MAX / 100); assert(Range >= NumCases); + if (TLI->isSuitableForJumpTable(SI, NumCases, Range)) { unsigned NumPartitions = 1 + (j == N - 1 ? 0 : MinPartitions[j + 1]); unsigned Score = j == N - 1 ? 0 : PartitionsScore[j + 1]; diff --git a/test/CodeGen/AArch64/max-jump-table.ll b/test/CodeGen/AArch64/max-jump-table.ll index 58bd6bebbfd..e6bdeb46149 100644 --- a/test/CodeGen/AArch64/max-jump-table.ll +++ b/test/CodeGen/AArch64/max-jump-table.ll @@ -10,15 +10,15 @@ declare void @ext(i32, i32) define i32 @jt1(i32 %a, i32 %b) { entry: switch i32 %a, label %return [ - i32 1, label %bb1 - i32 2, label %bb2 - i32 3, label %bb3 - i32 4, label %bb4 - i32 5, label %bb5 - i32 6, label %bb6 - i32 7, label %bb7 - i32 8, label %bb8 - i32 9, label %bb9 + i32 1, label %bb1 + i32 2, label %bb2 + i32 3, label %bb3 + i32 4, label %bb4 + i32 5, label %bb5 + i32 6, label %bb6 + i32 7, label %bb7 + i32 8, label %bb8 + i32 9, label %bb9 i32 10, label %bb10 i32 11, label %bb11 i32 12, label %bb12 @@ -30,33 +30,33 @@ entry: ] ; CHECK-LABEL: function jt1: ; CHECK-NEXT: Jump Tables: -; CHECK0-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 -; CHECK0-NOT: %jump-table.1: -; CHECK4-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 -; CHECK4-SAME: %jump-table.1: %bb.6 %bb.7 %bb.8 %bb.9 -; CHECK4-SAME: %jump-table.2: %bb.10 %bb.11 %bb.12 %bb.13 -; CHECK4-SAME: %jump-table.3: %bb.14 %bb.15 %bb.16 %bb.17 -; CHECK4-NOT: %jump-table.4: -; CHECK8-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 -; CHECK8-SAME: %jump-table.1: %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 -; CHECK8-NOT: %jump-table.2: -; CHECK16-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 -; CHECK16-NOT: %jump-table.1: -; CHECKM1-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 -; CHECKM1-SAME: %jump-table.1: %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 -; CHECKM1-NOT: %jump-table.2: -; CHECKM3-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 -; CHECKM3-NOT: %jump-table.1: - -bb1: tail call void @ext(i32 1, i32 0) br label %return -bb2: tail call void @ext(i32 2, i32 2) br label %return -bb3: tail call void @ext(i32 3, i32 4) br label %return -bb4: tail call void @ext(i32 4, i32 6) br label %return -bb5: tail call void @ext(i32 5, i32 8) br label %return -bb6: tail call void @ext(i32 6, i32 10) br label %return -bb7: tail call void @ext(i32 7, i32 12) br label %return -bb8: tail call void @ext(i32 8, i32 14) br label %return -bb9: tail call void @ext(i32 9, i32 16) br label %return +; CHECK0-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 +; CHECK0-NOT: %jump-table.1: +; CHECK4-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 +; CHECK4-SAME: %jump-table.1: %bb.6 %bb.7 %bb.8 %bb.9 +; CHECK4-SAME: %jump-table.2: %bb.10 %bb.11 %bb.12 %bb.13 +; CHECK4-SAME: %jump-table.3: %bb.14 %bb.15 %bb.16 %bb.17 +; CHECK4-NOT: %jump-table.4: +; CHECK8-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 +; CHECK8-SAME: %jump-table.1: %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 +; CHECK8-NOT: %jump-table.2: +; CHECK16-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 +; CHECK16-NOT: %jump-table.1: +; CHECKM1-NEXT: %jump-table.0: %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 +; CHECKM1-SAME: %jump-table.1: %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 +; CHECKM1-NOT: %jump-table.2: +; CHECKM3-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4 %bb.5 %bb.6 %bb.7 %bb.8 %bb.9 %bb.10 %bb.11 %bb.12 %bb.13 %bb.14 %bb.15 %bb.16 %bb.17 +; CHECKM3-NOT: %jump-table.1: + +bb1: tail call void @ext(i32 1, i32 0) br label %return +bb2: tail call void @ext(i32 2, i32 2) br label %return +bb3: tail call void @ext(i32 3, i32 4) br label %return +bb4: tail call void @ext(i32 4, i32 6) br label %return +bb5: tail call void @ext(i32 5, i32 8) br label %return +bb6: tail call void @ext(i32 6, i32 10) br label %return +bb7: tail call void @ext(i32 7, i32 12) br label %return +bb8: tail call void @ext(i32 8, i32 14) br label %return +bb9: tail call void @ext(i32 9, i32 16) br label %return bb10: tail call void @ext(i32 1, i32 18) br label %return bb11: tail call void @ext(i32 2, i32 20) br label %return bb12: tail call void @ext(i32 3, i32 22) br label %return @@ -72,28 +72,28 @@ 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 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: %jump-table.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{{$}} -; CHECK0-NOT: %jump-table.1 -; CHECK4-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} -; CHECK4-NOT: %jump-table.1 -; CHECK8-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} -; CHECK8-NOT: %jump-table.1 -; CHECK16-NEXT: %jump-table.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{{$}} -; CHECK16-NOT: %jump-table.1: -; CHECKM1-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} -; CHECKM1-NOT: %jump-table.1 -; CHECKM3-NEXT: %jump-table.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{{$}} -; CHECKM3-NOT: %jump-table.1 +; CHECK0-NEXT: %jump-table.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{{$}} +; CHECK0-NOT: %jump-table.1 +; CHECK4-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} +; CHECK4-NOT: %jump-table.1 +; CHECK8-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} +; CHECK8-NOT: %jump-table.1 +; CHECK16-NEXT: %jump-table.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{{$}} +; CHECK16-NOT: %jump-table.1: +; CHECKM1-NEXT: %jump-table.0: %bb.1 %bb.2 %bb.3 %bb.4{{$}} +; CHECKM1-NOT: %jump-table.1 +; CHECKM3-NEXT: %jump-table.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{{$}} +; CHECKM3-NOT: %jump-table.1 ; CHECK-DAG: End machine code for function jt2. bb1: tail call void @ext(i32 6, i32 1) br label %return @@ -108,10 +108,10 @@ return: ret void define void @jt3(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 1, label %bb1 + i32 2, label %bb2 + i32 3, label %bb3 + i32 4, label %bb4 i32 14, label %bb5 i32 15, label %bb6 @@ -144,18 +144,18 @@ entry: ; CHECKM3-NOT: %jump-table.1 ; CHECK-DAG: End machine code for function jt3. -bb1: tail call void @ext(i32 1, i32 12) br label %return -bb2: tail call void @ext(i32 2, i32 11) br label %return -bb3: tail call void @ext(i32 3, i32 10) br label %return -bb4: tail call void @ext(i32 4, i32 9) br label %return -bb5: tail call void @ext(i32 5, i32 8) br label %return -bb6: tail call void @ext(i32 6, i32 7) br label %return -bb7: tail call void @ext(i32 7, i32 6) br label %return -bb8: tail call void @ext(i32 8, i32 5) br label %return -bb9: tail call void @ext(i32 9, i32 4) br label %return -bb10: tail call void @ext(i32 10, i32 3) br label %return -bb11: tail call void @ext(i32 11, i32 2) br label %return -bb12: tail call void @ext(i32 12, i32 1) br label %return +bb1: tail call void @ext(i32 1, i32 12) br label %return +bb2: tail call void @ext(i32 2, i32 11) br label %return +bb3: tail call void @ext(i32 3, i32 10) br label %return +bb4: tail call void @ext(i32 4, i32 9) br label %return +bb5: tail call void @ext(i32 5, i32 8) br label %return +bb6: tail call void @ext(i32 6, i32 7) br label %return +bb7: tail call void @ext(i32 7, i32 6) br label %return +bb8: tail call void @ext(i32 8, i32 5) br label %return +bb9: tail call void @ext(i32 9, i32 4) br label %return +bb10: tail call void @ext(i32 10, i32 3) br label %return +bb11: tail call void @ext(i32 11, i32 2) br label %return +bb12: tail call void @ext(i32 12, i32 1) br label %return return: ret void } @@ -163,10 +163,10 @@ return: ret void define void @jt4(i32 %x) { entry: switch i32 %x, label %default [ - i32 1, label %bb1 - i32 2, label %bb2 - i32 3, label %bb3 - i32 4, label %bb4 + i32 1, label %bb1 + i32 2, label %bb2 + i32 3, label %bb3 + i32 4, label %bb4 i32 14, label %bb5 i32 15, label %bb6 @@ -199,18 +199,18 @@ entry: ; CHECKM3-NOT: %jump-table.1 ; CHECK-DAG: End machine code for function jt4. -bb1: tail call void @ext(i32 1, i32 12) br label %return -bb2: tail call void @ext(i32 2, i32 11) br label %return -bb3: tail call void @ext(i32 3, i32 10) br label %return -bb4: tail call void @ext(i32 4, i32 9) br label %return -bb5: tail call void @ext(i32 5, i32 8) br label %return -bb6: tail call void @ext(i32 6, i32 7) br label %return -bb7: tail call void @ext(i32 7, i32 6) br label %return -bb8: tail call void @ext(i32 8, i32 5) br label %return -bb9: tail call void @ext(i32 9, i32 4) br label %return -bb10: tail call void @ext(i32 10, i32 3) br label %return -bb11: tail call void @ext(i32 11, i32 2) br label %return -bb12: tail call void @ext(i32 12, i32 1) br label %return +bb1: tail call void @ext(i32 1, i32 12) br label %return +bb2: tail call void @ext(i32 2, i32 11) br label %return +bb3: tail call void @ext(i32 3, i32 10) br label %return +bb4: tail call void @ext(i32 4, i32 9) br label %return +bb5: tail call void @ext(i32 5, i32 8) br label %return +bb6: tail call void @ext(i32 6, i32 7) br label %return +bb7: tail call void @ext(i32 7, i32 6) br label %return +bb8: tail call void @ext(i32 8, i32 5) br label %return +bb9: tail call void @ext(i32 9, i32 4) br label %return +bb10: tail call void @ext(i32 10, i32 3) br label %return +bb11: tail call void @ext(i32 11, i32 2) br label %return +bb12: tail call void @ext(i32 12, i32 1) br label %return default: unreachable return: ret void diff --git a/test/CodeGen/AArch64/min-jump-table.ll b/test/CodeGen/AArch64/min-jump-table.ll index 5da3b022fa3..b5b7ff0777a 100644 --- a/test/CodeGen/AArch64/min-jump-table.ll +++ b/test/CodeGen/AArch64/min-jump-table.ll @@ -71,4 +71,3 @@ bb8: tail call void @ext(i32 8, i32 14) br label %return return: ret i32 %b } - -- 2.40.0